Longge's problem

旧城等待， 2022-01-08 00:25 85阅读 0赞

[Longge's problem][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;
    }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10885144.html

[Longge_s problem]: http://poj.org/problem?id=2480