目录
显示
题目链接
https://www.luogu.com.cn/problem/P2303
题解
设答案为 \(f(x)\)。
我们枚举 \(\gcd\) 的值:
$$f(x)=\sum_{d|x} d\sum_{i=1}^{x} [\gcd(i,x)=d]=\sum_{d|x}d \sum_{i=1}^{\frac{x}{d}}[\gcd(i,\frac{x}{d})=1]$$
容易发现后面的那个东西是 \(\varphi(\frac{x}{d})\),所以稍微变换一下:
$$f(x)=\sum_{d|x}d \cdot\varphi(\frac{x}{d})$$
写成 Dirichlet 卷积的形式就是:
$$f=\text{id}*\varphi$$
#include <iostream> using namespace std; long long n; long long phi(long long x) { long long ans=x,x1=x; for(long long i=2;i*i<=x1;i++) { if(x%i==0)ans=ans*(i-1)/i; while(x%i==0) x/=i; } if(x!=1)ans=ans*(x-1)/x; return ans; } long long f(long long x) { return x*phi(n/x); } int main() { long long ans=0; cin>>n; for(long long i=1;i*i<=n;i++) if(n%i==0) { if(i*i!=n)ans+=f(i)+f(n/i); else ans+=f(i); } cout<<ans<<endl; return 0; }