NUMTRY - Number Theory
f(n) and g(n) are two functions defined as following :
f(n) = ∏( pi2ei+1+1 ), where pi is prime factor of n and ei is highest power of pi in n.
g(n) = Σ( n/gcd(n,i) ); 1 <= i <= n
For a given value of n, you have to compute [f(n)/g(n)] % 1000000007.
Input
First line has T ( <= 10000 ), next T lines has 2 <= n <= 10^12.
Output
[f(n)/g(n)] % 1000000007 for each test case.
Example
Input: 2
2
4 Output:
3
3
Warning: Test cases aren't random. Test files consist of large primes, strong pseudo primes, Carmichael numbers, squares of primes, product of large primes, worst possible test cases for fermat, miller rabin and other primality testing algorithms.
Note: You may try the tutorial version ( same test files, 5s-100s time limit ).
hide comments
Francky:
2014-06-07 13:47:00
I did my best with python+psyco, and got tle, I haven't the best algo.
|
Added by: | XeRoN!X |
Date: | 2012-03-23 |
Time limit: | 0.100s-1.192s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Number Theory |