题解 P2303 【[SDOi2012]Longge的问题】
Siyuan
2019-02-08 10:54:50
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-SDOI-2012-Longge-Problem/)
---
## Description
> 题目链接：[Luogu 2303](https://www.luogu.org/problemnew/show/P2303)
Longge 的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $n$，你需要求出：
$$\sum_{i=1}^n\gcd(i,n)$$
数据范围：$1\le n\le 2^{32}$
------
## Solution
我们直接拆一下式子：
$$\begin{aligned}\text{原式}&=\sum_{i=1}^n\gcd(i,n) \\& =\sum_{d\mid n}d\times \sum_{i=1}^n [\gcd(i,n)=d] \\& =\sum_{d\mid n}d\times \sum_{i=1}^{\frac{n}{d}} \left[\gcd\left(i,\frac{n}{d}\right)=1\right] \\ \\& =\sum_{d\mid n}d\cdot \varphi(\frac{n}{d}) \\\end{aligned}$$
这个转化的过程非常套路，我们只要暴力枚举 $n$ 的因数并快速求出单个 $\varphi$ 函数的值即可。
**时间复杂度**：$O(\text{因子个数}\times \sqrt n)$（稳过 QAQ）
------
## Code
```cpp
#include <cstdio>
#include <cmath>
const int N=(1<<16)+5;
int n,tot,p[N];
bool flg[N];
void sieve(int n) {
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
long long phi(long long x) {
long long ans=x;
for(int i=1;i<=tot&&1LL*p[i]*p[i]<=x;++i) {
if(x%p[i]) continue;
ans=ans/p[i]*(p[i]-1);
while(x%p[i]==0) x/=p[i];
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
int main() {
long long n,ans=0;
scanf("%lld",&n);
sieve((int)sqrt(n));
for(long long i=1;i*i<=n;++i) {
if(n%i==0) {
ans+=i*phi(n/i);
if(i*i!=n) ans+=n/i*phi(i);
}
}
printf("%lld\n",ans);
return 0;
}
```