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 10^9+7.
Example
Input: 1 5 6 Output: 5760
hide comments
smtcoder:
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.... :) |
|
nehae:
2016-09-02 22:41:39
any other approach except memoization? |
|
Sarthak Munshi:
2016-09-02 21:07:00
memoization should help :) |
|
abobakr_pp:
2016-08-17 19:57:19
Is there a common formula for this sequence :-
|
|
Rishav Goyal:
2016-08-16 06:06:39
@author : n > 5000000. look into test files. input files are wrong. please correct them asap.
|
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 |