「SDOI 2012」Longge 的问题

Description

题目链接：BZOJ 2705

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

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