Question 问题 P2568 GCD
\[\sum_{p\in prime}\sum_{i=1}^n \sum_{j=1}^n [\gcd(i, j)==p]
\]
Analysis 分析 1
（所以肯定有第二种思考的方法，看后面（目前没写））
变形
\[\sum_{p\in prime}\sum_{i=1}^{\lfloor{\frac n p}\rfloor} \sum_{j=1}^{\lfloor{\frac n p}\rfloor} [\gcd(i, j)==1]
\]
改变枚举上界
\[\sum_{p\in prime}(\sum_{i=1}^{\lfloor{\frac n p}\rfloor}(2\sum_{j=1}^i[gcd(i,j)==1])-1)
\]
容易发现后面的 \(\sum_{j=1}^i[gcd(i,j)==1]\) 就是 \(\varphi(i)\) 替换一下
\[\sum_{p\in prime}(2\sum_{i=1}^{\lfloor{\frac n p}\rfloor}\varphi(i)-1)
\]
至此，该式子变换已经结束
我们只需要通过线性筛出 \(\varphi(i)\) 和 \(prime\)
做一个前缀和后 枚举所有\(p\in prime\) 并且 \(p\le n\)的所有情况就结束了
Code 代码
线性筛部分
void init(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!f[i]) phi[i]=i-1,prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
f[prime[j]*i]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
主函数
int main(){
cin>>n;init();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
for(int i=1;i<=cnt;i++) ans+=2*sum[n/prime[i]]-1;
cout<<ans;
return 0;
}