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}\)
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
Editorial