传送门 考虑每一个质数 P 对答案的贡献 gcd(x,y) = P，不妨设 $x\geqslant y$ 那么 $gcd(\frac{x}{P},\frac{y}{P})=1$ 对于每一个 $\frac{x}{P}$，贡献就是求小于等于它的数中与它互质的数的个数，即 $\
传送门
考虑每一个质数 P 对答案的贡献
gcd(x,y) = P，不妨设 $x\geqslant y$
那么 $gcd(\frac{x}{P},\frac{y}{P})=1$
对于每一个 $\frac{x}{P}$，贡献就是求小于等于它的数中与它互质的数的个数，即 $\phi_{\frac{x}{P}}$
显然 $\frac{x}{P} \leqslant \frac{n}{P}$
那么就是求每一个小于等于 $\left \lfloor \frac{n}{P} \right \rfloor$ 的 $t$ 的 $\phi_t$ 之和
对每一个质数 P 都要求一次
可以用前缀和优化，复杂度O(n)
注意此时是 $x\geqslant y$ 的情况，要把答案乘2后减去 $x=y$ 的情况
显然 $x=y$ 只有当 $x=y=P$ 的时候
所以要减去小于等于 n 的质数个数
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e7+7; int n; int pri[N],tot; ll phi[N],ans; bool not_pri[N]; void pre()//线性筛欧拉函数 { not_pri[1]=1; phi[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[i]) { pri[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot;j++) { ll g=pri[j]*i; if(g>n) break; not_pri[g]=1; if(!(i%pri[j])) { phi[g]=phi[i]*pri[j]; break; } else phi[g]=phi[i]*phi[pri[j]]; } } for(int i=2;i<=n;i++) phi[i]+=phi[i-1];//搞成前缀和 } int main() { n=read(); pre(); for(int i=1;i<=tot;i++) ans+=phi[n/pri[i]]; cout<<ans*2-tot; return 0; }