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 ??
Google the properties of modulo arithmetic and see if you can figure out how to modify the standard GCD algorithm accordingly.
Topic archived. No new replies allowed.