SUMUP2 - Integer Factorization With A Twist

no tags 

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.

I had strong suspicion based on others' submissions that the test data is far from conforming to uniform distribution over [2, 10^15]. I find that in the large input file, the average of log(K)/log(10) is between 8 and 9.

My opinion remains that the problem is poorly made, by someone who is probably not very familiar with factoring algorithms and optimisation. There are many strange things/red flags. I certainly wouldn't mind to see it get moved to tutorial.

To the problem setter's credit, he/she hasn't deleted any of our criticising comments, which is nice.

Last edit: 2012-07-01 14:04:17
(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...
Although this problem has 10000 integer but it not all 15 digit and not all is pseudo-primes, rho need ~4s to solve this problem...

Rajesh Kumar: 2012-07-06 19:46:33

@Those who solved this one -
I could solve the tutorial version in 3.83 s where there are only 100 test cases..
here we have 10000.. ny hint how to solve this one???
Just tell whether Pollard rho + Miller rabbin work or not??

Last edit: 2012-07-01 08:35:38
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.

For your problem, sorry to insist, but I think you should put it in tutorial. And I think only 'a big boss' can propose that kind of problem ; it's just my poor cent opinion. You should know that factoring problems are 'sensible'. For me solve FACT0 or another similar isn't enough to be 'a big boss'.

Regards.

Last edit: 2012-06-30 19:28:08
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.

But the discussion gets a little off-topic. The problem is allowed by the editorial board, and it could still be instructive regardless of quality concerns. So, live and let live.

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
becomes a difficult problem in this time limit,and a naive algo will never get accepted here.


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