could any one post code for the followong question.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
could any one post code for the followong question.
Name |
---|
This question is pretty simple if you have Pollard Rho algorithm in your library. It's a straight copy and paste.
Here you go :
http://ideone.com/3dnYAv
Note: I think there is some way ( which I don't know ) to solve this question without this algorithm.
Blog Post
First remove all prime factors that are less than 10^6. Let x be the resulting number. Now check if x is prime or not using miller-rabin. If it is prime then we already have the prime factorization. If x is not prime we know that the remaining prime factors are greater than 10^6, therefore it must have exactly two prime factors (since having 3 or more would yield a number greater than 10^18). Now we need to know whether those prime factors are equal or not, we can simply check if x is a square or not, we can do this be testing if x == pow(int(sqrt(x) + .5), 2). With these you should be able to get the number of divisors.
Correct me if I'm wrong, but isn't miller rabin unreliable especially for programming contests?
Depends on the implementation, you can guarantee that the algorithm will work up to certain value. Here is an example that will work for numbers up to 3*10^18:
http://pastebin.com/6XEFRPaZ
Is it garanteed that x == pow(int(sqrt(x) + .5), 2) works for every case (precision loss)?? I remember doing something similar and getting wrong answer, so I just iterated from sqrt(x)-5 till sqrt(x)+5 to avoid that, though probably sqrt(x) and sqrt(x)+1 are enough.
here is a recent blog post by himanshujaju.