| Submit | All submissions | Best solutions | Back to list |
PROD1GCD - Product it again |
The problem is very simple. given two integers n and m, find the product GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M).
Input
The first line will be the number of test cases t, followed by t lines, each having two numbers n and m (1 ≤ n, m ≤ 10000000) (1 ≤ t ≤ 5).
Output
Output the required solution modulo 109+7.
Example
Input: 1 5 6 Output: 5760
| Added by: | Abhinandan Agarwal |
| Date: | 2016-08-15 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU |
hide comments
|
2016-10-09 15:30:53
Question isn't that tough..NO Euler's Totient needed....just find patterns..try to squeeze as many calculations as possible and u r done wid it.... :) |
|
|
2016-09-02 22:41:39
any other approach except memoization? |
|
|
2016-09-02 21:07:00 Sarthak Munshi
memoization should help :) |
|
|
2016-08-17 19:57:19
Is there a common formula for this sequence :- gcd(1,n)*gcd(2,n)...*gcd(m,n) for two positive integers n,m ? RE: not particularly, my solution is not O(1). Well, if you want, you can still try :-) Last edit: 2016-08-17 20:40:40 |
|
|
2016-08-16 06:06:39 Rishav Goyal
@author : n > 5000000. look into test files. input files are wrong. please correct them asap. RE: sorry for the inconvenience, I have updated the constraints, its 10^7 now ! Last edit: 2016-08-16 15:21:36 |
RSS