[洛谷 2303][SDOI2012]Longge的问题

题目链接

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;
}