KGCD
Practice
3.7 (27 votes)
Mathematics
Medium
Problem
65% Success 1541 Attempts 30 Points 10s Time Limit 256MB Memory 1024 KB Max Code

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 \(1 \le a \le N\), \(1 \le b \le N\). 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:

  • \(1 \le T \le 10\)
  • (20 points): \(1 \le N \le 1000\)
  • (30 points): \(1 \le N \le 10^6\)
  • (50 points): \(1 \le N \le 10^{12}\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
11 votes
Tags:
AlgorithmsApprovedData StructuresEasyHash MapsHash TablesMapsOpenString Manipulationapproved
Points:20
6 votes
Tags:
MathematicsEasyMathematicsMathematicsMathamatics
Points:20
615 votes
Tags:
ApprovedDynamic ProgrammingEasyMathReady