签到题 III
题目背景
pj组选手zzq近日学会了求最大公约数的辗转相除法。
题目描述
类比辗转相除法,zzq定义了一个奇怪的函数:
```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;
}
```
zzq定义完这个函数兴高采烈,随便输入了两个数,打算计算f值,发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。
现在zzq输入了一个数n,想要求出$\sum_{i=1}^n \sum_{j=1}^n f(i,j)$。
输入输出格式
输入格式
一行一个数n。
输出格式
一行一个数$\sum_{i=1}^n \sum_{j=1}^n f(i,j)$。
输入输出样例
输入样例 #1
100
输出样例 #1
1124
输入样例 #2
2000
输出样例 #2
68204
说明
对于10%的数据,$n \leq 300$。
对于40%的数据,$n \leq 2000$。
对于70%的数据,$n \leq 5 \times 10^5$。
对于100%的数据,$1 \leq n \leq 5 \times 10^{11}$。