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
|
Francky:
2012-07-06 19:46:33
@ .:.:.:.sTiLl aLiVe.:.:.:. :
|
|
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/
|
|
|
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.
|
|
NeW AcP:
2012-07-06 19:46:33
time can be more strict. upto 2 sec.
|
|
|
Francky:
2012-07-06 19:46:33
@Tjandra : I agree with you too.
|
|
|
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.
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-07-06 19:46:33
I bet no one can solve this problem with this time limit :P
|
| 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