Wait for it
All submissions for this problem are available.
Given N, A and B, find the value of the following expression:
Since the value can be large, find it modulo (109+7).
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line containing three space-separated integers — A, B, and N.
- For each test case, output a single line containing the value of the expression modulo 109+7.
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 109
- 1 ≤ B < A ≤ 109
- GCD(A,B) = 1, i.e., A and B are coprime.
Input: 2 3 2 2 2 1 2 Output: 8 6
Example case 1.The summation expands to gcd(1,1) + gcd(5,1) + gcd(1,5) + gcd(5,5) = 8.
Example case 2.The summation expands to gcd(1,1) + gcd(3,1) + gcd(1,3) + gcd(3,3) = 6.
|Tags||acm15kol, euclidean, eulerian, gcd, piyushkumar, totient|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.