KGCD

3.7

27 votes
Mathematics, Medium
Problem

Kevin recently learned a new algorithm called Greatest Common Divisor. He tried to implement it but he failed. He called this new algorithm Kevin's Greatest Common Divisor (KGCD). You can look at this implementation:

long long kgcd(long long a, long long b)
{
    while (a > 0 && b > 0)
    {
        a -= b;
        swap(a , b);
    }
    return a + b;
}

Now Kevin runs kgcd(a,b) for all 1aN, 1bN. He is interested in how many times his algorithm returns the correct gcd value of a and b.

Input format:

The first line of input will contain an integer T, denoting the number of test cases.
Each of the next T lines contain one integer N.

Output format:

For every test case output the number of times kgcd(a,b)==gcd(a,b).

Constraints:

  • 1T10
  • (20 points): 1N1000
  • (30 points): 1N106
  • (50 points): 1N1012
Sample Input
2
4
2
Sample Output
14
4
Time Limit: 10
Memory Limit: 256
Source Limit:
Explanation

In the first case kgcd works correct for all a,b except (2,3) and (3,4).

Editor Image

?