P3764 Check-in Problem III

The Junior contestant zzq recently learned the Euclidean algorithm for computing the greatest common divisor (GCD).

By analogy with the Euclidean algorithm, zzq defined a strange function: ```cpp typedef long long ll; ll f(ll a,ll b) { if(a==b) return 0; if(a>b) return f(a-b,b+b)+1; else return f(a+a,b-a)+1; } ``` After defining this function, zzq excitedly entered two numbers to compute the value of $f$, but found that the function fell into an infinite recursion... Therefore, zzq defines the value of $f$ to be $0$ in cases where the recursion would loop infinitely. Now zzq inputs a number $n$, and wants to compute $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$.

One line containing an integer $n$.

One line containing an integer $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$.

For 10% of the testdata, $n \leq 300$. For 40% of the testdata, $n \leq 2000$. For 70% of the testdata, $n \leq 5 \times 10^5$. For 100% of the testdata, $1 \leq n \leq 5 \times 10^{11}$. Translated by ChatGPT 5