多组测试数据，每组测试数据给你一个正整数 \(n\)，让你求满足 \(\gcd(i,j) = 1\) 并且 \(1\le i < j \le n\) 的数对个数。
随便想一想，得出一个递推式：\(F_n = F_{n-1} + \varphi(n)\)。证明很简单：\(F_n\) 是包含 \(F_{n-1}\) 的，多出来的部分就是小于 \(n\) 并且和 \(n\) 互质的数的个数。而这一部分，就是 \(\varphi(n)\)。
递推初始条件：\(F_0=0\)，这里举一个计算 \(F_3\) 的例子：
\[\begin{aligned} F_3 &= F_2+\varphi(3)\\ &= F_1+\varphi (2) +\varphi(3)\\ &=F_0+\varphi(1)+\varphi (2)+\varphi(3)\\ &=\varphi(1)+\varphi (2)+\varphi(3) \end{aligned}\]所以我们得出结论：
\[F_n = \varphi (1) + \varphi (2) +\varphi (3) +\varphi (4) +\cdots +\varphi (n) \]然后就非常快乐地开始写代码了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long Prime[1000010],phi[1000010];
bool vis[1000010];
long long cnt,n;
void init(int n)
{
phi[1]=1;
for(int i= 2;i<=n;i++){
if(vis[i]==0){
Prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){
vis[Prime[j]*i]=1;
if(i%Prime[j]==0){
phi[Prime[j]*i]=phi[i]*Prime[j];
break;
}
else{
phi[Prime[j]*i]=phi[Prime[j]]*phi[i];
}
}
}
}
signed main(){
init(1000005);
while(1){
long long n;
cin>>n;
if(n==0){
return 0;
}
long long sum=0;
for(int i=2;i<=n;i++){
sum+=phi[i];
}
cout<<sum<<endl;
}
}