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
Yashpal:
2014-12-31 19:55:28
Awesome Problem !! Reduced in Simple formula ! :) Last edit: 2014-12-31 20:16:47 |
|
Viplov Jain:
2014-06-22 15:29:09
@xeronix please provide information on test files like given on this page ->http://www.spoj.com/problems/APS2/
|
|
[Lakshman]:
2014-06-07 13:47:00
Finally accepted took three moths to solve this problem.
|
|
[Lakshman]:
2014-06-07 13:47:00
@XeRo!NiX My new Solution seems faster than 2 accepted users in easy version but here TLE, Do the easy version have different input files?
|
|
[Lakshman]:
2014-06-07 13:47:00
@XeRo!NiX can you please suggest me some optimistion Last edit: 2014-02-25 08:36:21 |
|
apia:
2014-06-07 13:47:00
It seems my total time is faster than Damian Straszak,but I got TLE again.
|
|
teoy:
2014-06-07 13:47:00
the time limit is for one case or all cases ? |
|
Damian Straszak:
2014-06-07 13:47:00
the tutorial version is very helpful, thank you |
|
Damian Straszak:
2014-06-07 13:47:00
Ok, so this is tough. I Have no idea how to speed up my code. Any hints :)? |
|
Damian Straszak:
2014-06-07 13:47:00
It's pretty hard to factorize n, when the time limit is so strict... (btw. why not equal limits for all testcases?).
|
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 |