Modular GCD problem of codechef
Given integers A, B and N, you should calculate the GCD of A^N+B^N and |A−B|. (Assume that GCD(0,a)=a for any positive integer a). Since this number could be very large, compute it modulo 1000000007 (10^9+7).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains three space-separated integers A, B and N.
Output
For each test case, print a single line containing one integer — the required GCD modulo 10^9+7.
Constraints
1≤T≤10
1≤A,B,N≤1012
B≤A
Can anyone please give me the idea to solve this problem ??
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains three space-separated integers A, B and N.
Output
For each test case, print a single line containing one integer — the required GCD modulo 10^9+7.
Constraints
1≤T≤10
1≤A,B,N≤1012
B≤A
Can anyone please give me the idea to solve this problem ??
Topic archived. No new replies allowed.