TRENDGCD - Trending GCD
Problem statement is simple. Given A and B you need to calculate S(A, B).
Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1.
Input
The first line contains one integer T - denoting the number of test cases.
T lines follow each containing two integers A, B.
Output
For each testcase output the value of S(A, B) mod 1000000007 in a single line.
Constraints
- T <= 1000
- 1 <= A, B <= 1000000
Example
Input: 3 42 18 35 1 20 25 Output: 306395 630 128819
hide comments
minimixer:
2019-09-25 11:15:34
The intended solution is supposed to be O(N+T*N^1/2)
|
|
rainy jain :
2016-06-03 02:53:21
@Adarsh what is the expected complexity? |
|
jame_:
2016-04-18 23:26:05
getting TLE any suggestion |
Added by: | Adarsh kumar |
Date: | 2016-01-04 |
Time limit: | 0.300s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |