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
Francky: 2012-07-06 19:46:33

@ .:.:.:.sTiLl aLiVe.:.:.:. :
no, for me it's too late, it should have be done before. More, for me me the problem setter is burned at my eyes, as he submit someone else solution in my REBOUND problem, ...
My wish is : Robert Gerbicz or another authority propose this problem with a not weak input file, ie full of strong pseudo-primes, and not just random numbers. That's make sense for me.

RE -> Sir, they both are my id. If u want I can show u the proof too.

Last edit: 2012-06-30 10:23:37
Rajesh Kumar: 2012-07-06 19:46:33

@Francky - So now the problem setter has to solve 100 problems(Number Theory) in next 5 days to show his capabilities..?? :D :D

Mitch Schwartz: 2012-07-06 19:46:33

Yeah, I'm with Francky. I submitted some of my old code just to see, but I won't submit new code unless problem setter is more trustworthy. The fact that time limit kept being changed reinforces my belief (it's just a belief) that problem setter doesn't know much about the subject material.

Francky: 2012-07-06 19:46:33

A clone problem : http://www.spoj.pl/problems/FACTSUM/
yet in tutorial with reason.
Before posting a problem, problem setter should have shown its capabilities. So, I'll do with pleasure this problem if the problem setter is better known, sorry.

Last edit: 2012-06-30 09:36:42
Rajesh Kumar: 2012-07-06 19:46:33

Will Pollard rho + miller rabbin work here...??

:D: 2012-07-06 19:46:33

It seems the problem is solvable. It's pretty much a clone but it require way better implementation than the ones before. We allowed that kind of problem pairs/triples in the past, so I'm leaving it for now. I will keep track of what other users think about it.

RE -> Sir, give it a try. It's worth it !!!

Last edit: 2012-06-30 09:17:09
NeW AcP: 2012-07-06 19:46:33

time can be more strict. upto 2 sec.
RE -> DONE :D

Last edit: 2012-06-30 04:08:42
Francky: 2012-07-06 19:46:33

@Tjandra : I agree with you too.
The problem setter should solve FACT0 or FACT1 in a ultra speed way before submitting such a problem.
Edit : +1 with Mitch.

Last edit: 2012-06-29 17:14:30
Mitch Schwartz: 2012-07-06 19:46:33

It seems strange to me. The task is just a clone of FACT0 with trivial calculation attached--not much of a "twist". The constraints are very tight, yet the problem setter hasn't shown any proficiency in factoring or number theory problems according to submission history. For an advanced number theory problem, there's no need to explain that 1 is not prime. Regarding language restriction, I don't think it can be assumed that C/C++ are the only languages fast enough to pass, so that's strange as well.


RE -> Sir, I haven't done those problems doesn't means that I can't do it !!!

Last edit: 2012-06-30 09:16:00
(Tjandra Satria Gunawan)(曾毅昆): 2012-07-06 19:46:33

I bet no one can solve this problem with this time limit :P

RE -> Sir, 3 fellows have done it. You have lost the bet :D

Last edit: 2012-06-30 09:13:00

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