洛谷 - P1390 - 公约数的和 - 莫比乌斯反演

https://www.luogu.org/problemnew/show/P1390

求 $\sum\limits_{i=1}^{{n}\sum\limits_{j=1}}{m} gcd(i,j) $

不会,看题解:

类似求gcd为p的求法:

$ f(n) = \sum\limits_{i=1}^{{n}\sum\limits_{j=1}}{m} gcd(i,j) =\sum\limits_{i=1}^{N} d \sum\limits_{i=1}^{{n}\sum\limits_{j=1}}{m} [gcd(i,j)==d] $

提出 $d$ :

$ f(n) =\sum\limits_{i=1}^{N} d \sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor }\sum\limits_{j=1}^{ \lfloor\frac{m}{d}\rfloor } [gcd(i,j)==1] $

用 $\sum\limits_{d|n}\mu(d)=[n==1] $ 替换,反演:

$ f(n) = \sum\limits_{i=1}^{N} d \sum\limits_{k=1}^{N} \mu(k) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor $

记 $T=kd$ :

$ f(n) = \sum\limits_{T=1}^{N} \sum\limits_{d|T} d \mu(\frac{T}{d}) \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor $

提出 $T$

$ f(n) = \sum\limits_{T=1}^{N} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \sum\limits_{d|T} d \mu(\frac{T}{d}) $

因为:

$\sum\limits_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n} $

$ f(n) = \sum\limits_{T=1}^{N} \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \varphi(T) $

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 2000005

int phi[N],pri[N],cntpri=0;

bool notpri[N];

void sieve_phi(int n)

{

    notpri[1]=phi[1]=1;

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

    {

        if (!notpri[i]) pri[++cntpri]=i,phi[i]=i-1;

        for (int j=1;j<=cntpri&&i*pri[j]<=n;j++)

        {

            notpri[i*pri[j]]=1;

            if (i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]];

            else {phi[i*pri[j]]=phi[i]*pri[j];break;}

        }

    }

}

int main(){

    int n;

    cin>>n;

    sieve_phi(n);

    ll ans=0;

    for(int i=1;i<=n;i++){

        ans+=1ll*phi[i]*(n/i)*(n/i);

    }

    cout<<(ans-(1ll*(1+n)*n)/2)/2<<endl;

}

另一种奇怪的做法:

$ f(n) = \sum\limits_{d=1}^{n} d \sum\limits_{i=1}^{{n}\sum\limits_{j=1}}{i-1} [gcd(i,j)==d] $

提d:

$ \sum\limits_{d=1}^{n} d \sum\limits_{i=1}^{{\frac{n}{d}}\sum\limits_{j=1}}{i-1} [gcd(i,j)==1] $

后面是欧拉函数的定义:

$ \sum\limits_{d=1}^{n} d \sum\limits_{i=2}^{\frac{n}{d}} \varphi(i) $

这里有个bug是因为1和1互质但是1和1相同，所以要去掉 $\varphi(1)$

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 2000000+5

int phi[N],pri[N],cntpri=0;

bool notpri[N];

ll prefix[N];

void sieve_phi(int n) {

    notpri[1]=phi[1]=1;

    prefix[0]=0;

    prefix[1]=1;

    for(int i=2; i<=n; i++) {

        if(!notpri[i])

            pri[++cntpri]=i,phi[i]=i-1;

        for(int j=1; j<=cntpri&&i*pri[j]<=n; j++) {

            notpri[i*pri[j]]=1;

            if(i%pri[j])

                phi[i*pri[j]]=phi[i]*phi[pri[j]];

            else {

                phi[i*pri[j]]=phi[i]*pri[j];

                break;

            }

        }

        prefix[i]=prefix[i-1]+phi[i];

    }

}

ll solve(ll n){

    ll ans=0;

    for(int d=1;d<=n;d++){

        ans+=d*((prefix[n/d])-1);

    }

    return ans;

}

int main() {

    sieve_phi(2000000+1);

    int n;

    while(cin>>n) {

        ll ans=solve(n);

        cout<<ans<<endl;

    }

}

巴特西

洛谷 - P1390 - 公约数的和 - 莫比乌斯反演 - 欧拉函数

最新文章

热门文章