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

· · 题解

化一化式子

\sum\limits_{i=1}^n\gcd(i,n)=\sum\limits_{d|n}d\sum\limits_{i=1}^n[\gcd(i,n)=d]=\sum\limits_{d|n}d\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]=\sum\limits_{d|n}d\varphi(\frac{n}{d})

也就是id\ast\varphi

考虑把\varphi拆开，那么得到

n\sum\limits_{d|n}\prod\limits_{p|d}\frac{p-1}{p}

令n=\prod\limits_ip_i^{k_i}，设S=\{p_i\}

考虑d中包含哪些p_i，枚举所有S的子集，那么这样的子集对应的d一共有\prod k_i个，要求所有子集的贡献之和.

稍微思考一下可以知道答案是n\prod\limits_i(k_i\cdot\frac{p_i-1}{p_i}+1)，就是分别考虑每个元素选和不选对答案的贡献.于是分解质因数之后计算.

O(\sqrt{n}) 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long ans=1,n;
int main()
{
    scanf("%lld",&n);long long nn=n;//解决分数的问题，从外面的n里抽出一个pi给内部
    for(long long i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            nn/=i;int t=0;
            while(n%i==0)++t,n/=i;
            ans=ans*(t*(i-1)+i);
        }
    }
    if(n!=1)nn/=n,ans=ans*(2*n-1);
    cout<<ans*nn<<endl;
}

如果把n改小一些多次询问就照着上面的式子线筛一下就好了，或者直接卷积O(n\log n)也行