| 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
|
||||||
|
2022-04-01 11:08:39
AC in 0.07s :) |
||||||
|
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. |
||||||
|
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 |
||||||
|
2012-07-06 19:46:33 Mitch Schwartz
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 |
||||||
|
2012-07-06 19:46:33 (Tjandra Satria Gunawan)(曾毅昆)
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... |
||||||
|
2012-07-06 19:46:33 Rajesh Kumar
@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 |
||||||
|
2012-07-06 19:46:33 NeW AcP
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 |
||||||
|
2012-07-06 19:46:33 Francky
@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 |
||||||
|
2012-07-06 19:46:33 Mitch Schwartz
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. |
||||||
|
2012-07-06 19:46:33 NeW AcP
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. |
||||||
RSS