HH is learning GCD today, GCD is short for Greatest Common Divisor. You can look at this implementation:
long long gcd(long long a, long long b){
while(a > 0 && b > 0){
a %= b;
swap(a , b);
}
return a + b;
} But HH is so careless that he changes "%" into "-", let's call this new funtion HH′s Greatest Common Divisor (HGCD). You can look at this implementation:
long long hgcd(long long a, long long b) {
while (a > 0 && b > 0) {
a -= b;
swap(a , b);
}
return a + b;
} Now HH run HGCD(a,b) for all 1≤a≤n, 1≤b≤n,HH wants to know how many times does his algorithm - HGCD works correctly.
Note:
void swap(long long &a, long long &b){
long long t = a;
a = b; b = t;
}