Longge's problem

求\(\sum_{i=1}^ngcd(i,n)\),\(n< 2^{31}\)。

解

理解1：

注意式子的实际意义，显然答案只可能在n的约数中，而现在问题变成了每个约数出现了几次,而一个约数d要出现的次数，自然需要这个数有约数d，其他的约数与之互斥，于是考虑欧拉函数，故我们有

\[ans=\sum_{d|n}\varphi(n/d)d
\]

以此枚举n的约数爆算即可，时间复杂度不难得知为\(O(\sigma(n)\sqrt{n})\)。

理解2：

约数计数问题，考虑反演，于是有

\[ans=\sum_{d=1}^nd\sum_{i=1}^n(gcd(i,n)==d)
\]

设

\[f(d)=\sum_{i=1}^n(gcd(i,n)==d)
\]

\[F(d)=[n/d](d|n)
\]

由Mobius反演定理，带入原式我们有

\[ans==\sum_{d=1}d\sum_{d|x,x|n}[n/x]\mu(x/d)=
\]

\[\sum_{x|n}[n/x]\sum_{d|x}d\mu(x/d)=\sum_{x|n}[n/x]\varphi(x)
\]

同理解1做法即可。

于是我们可以小结一下，同排列组合一样，约数计数问题，也有它的实际意义的理解，两者侧重点不同，一个侧重思维，一个侧重代数变换，但是殊途同归，而且不难得知最后的答案其实就是\(\varphi *id\)，我们可以使用杜教筛对之优化，数据范围可以出到\(10^{11}\)，但无论如何，重点都在于对于约数的巧妙的理解。

参考代码：

#include <iostream>

#include <cstdio>

#define il inline

#define ri register

#define ll long long

using namespace std;

il ll Phi(ll);

int main(){

    ll ans,n,i;

    while(scanf("%lld",&n)!=EOF){

        for(ans&=0,i=1;i*i<n;++i)

            if(!(n%i)){

                ans+=(n/i)*Phi(i);

                ans+=(i)*Phi(n/i);

            }

        if(i*i==n)ans+=i*Phi(i);

        printf("%lld\n",ans);

    }

    return 0;

}

il ll Phi(ll n){

    ri ll i,ans(n);

    for(i=2;i<=n/i;++i)

        if(!(n%i)){

            (ans/=i)*=(i-1);

            while(!(n%i))n/=i;

        }if(n>1)(ans/=n)*=(n-1);

    return ans;

}

巴特西

Longge's problem

解

最新文章

热门文章