题解 P2303 【[SDOi2012]Longge的问题】

· · 题解

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