| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
||||||
|
2012-07-06 19:46:33 Francky
@ .:.:.:.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 |
||||||
|
2012-07-06 19:46:33 Rajesh Kumar
@Francky - So now the problem setter has to solve 100 problems(Number Theory) in next 5 days to show his capabilities..?? :D :D |
||||||
|
2012-07-06 19:46:33 Mitch Schwartz
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. |
||||||
|
2012-07-06 19:46:33 Francky
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 |
||||||
|
2012-07-06 19:46:33 Rajesh Kumar
Will Pollard rho + miller rabbin work here...?? |
||||||
|
2012-07-06 19:46:33 :D
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 |
||||||
|
2012-07-06 19:46:33 NeW AcP
time can be more strict. upto 2 sec. RE -> DONE :D Last edit: 2012-06-30 04:08:42 |
||||||
|
2012-07-06 19:46:33 Francky
@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 |
||||||
|
2012-07-06 19:46:33 Mitch Schwartz
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 |
||||||
|
2012-07-06 19:46:33 (Tjandra Satria Gunawan)(曾毅昆)
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 |
||||||
RSS