SUMUP2 - Integer Factorization With A Twist
Given a positive integer (K > 2), with prime factorization:
K = p1^a1 * p2^a2 ... * pn^an (Excluding 1)
Compute the following:
S = a1*p1 + a2*p2 ... + an*pn.
Input
A integer K on each line (2 <= k <= 10^15).
Take input until EOF has occurred.
Output
For each integer compute the S = a1*p1 + a2*p2 ... + an*pn and output it on a single line.
Example
Input: 6 7 1804289385 846930888 1681692779 1714636917 Output: 5 7 120285967 18767 360709 1008039
WARNING: There are more than 10000 integers in the test file, use I/O optimization too.
hide comments
|
manoj0606:
2022-04-01 11:08:39
AC in 0.07s :) |
|
lighted:
2020-10-24 09:25:44
Solution with int type for answer got accepted. It seems that there is no prime number in input greater 2^31-1 or prime factor greater 2^31-1. |
|
|
lighted:
2020-10-24 09:02:50
I got accepted with simple O(sqrt(n)) factorization in 0.48s. Time limit is 1s. Maybe it's because of weak test cases as someone mentioned. It's strange why people get TLE. FACT0 also accepted in same way. Got TLE for FACTSUM and FACT1. Last edit: 2020-10-24 09:03:33 |
|
Mitch Schwartz:
2012-07-06 19:46:33
Despite misgivings, I decided to submit some slightly newer code (still lacking many optimisations). Pollard's rho with Miller-Rabin can pass with scanf/printf.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-07-06 19:46:33
It not work, I used Miller Rabbin + Pollard Rho on this problem and I'm getting TLE... To solve this problem we need an algorithm that 2x faster than Pollard Rho+Miller Rabbin... maybe quadratic sieve will pass...
|
|
Rajesh Kumar:
2012-07-06 19:46:33
@Those who solved this one -
|
|
NeW AcP:
2012-07-06 19:46:33
I still not think with this strict time limit it is an easy problem,to solve,it should,it must remain in the classical section.btw,there is already an tutorial version with much higher time limit .so, no need to add another there only.there is no need to become a big boss for setting any kind of problem. Last edit: 2012-07-01 01:30:51 |
|
Francky:
2012-07-06 19:46:33
@snehasish_roy : if it's both your id, then you should disqualified all submissions of one of them. I read the forum, but I don't understand the reasons to have two account.
|
|
|
Mitch Schwartz:
2012-07-06 19:46:33
Eh, I don't think setting problems you can't solve is a good idea. If it's from an official contest and you test with official solutions, or if you are friends with the author who is knowledgeable, then you could possibly get away with it. But in general you won't be able to ensure the quality of the problem or test data or constraints, or even ensure that the problem is solvable.
|
|
|
NeW AcP:
2012-07-06 19:46:33
I don't think for setting the problem it is necessary for the problem setter to solve it.Problem is creation of problem setter and it doesn't really matter if he changes it's time limit .this problem
|
| Added by: | Better late than never !!! |
| Date: | 2012-06-29 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C C++ 4.3.2 CPP C99 |
| Resource: | RamjiLal Sir |
RSS