$$\Large\texttt{My Blog}$$


Description

题目链接:Luogu 2303

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