洛谷 - UVA11424 - GCD - Extreme (I) - 莫比乌斯反演

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

原本以为是一道四倍经验题来的。

因为输入的n很多导致像之前那样 \(O(n)\) 计算变得非常荒谬。

那么我们就需要引入一个整除分块！

首先预处理欧拉函数的前缀和，然后丢进分块里面搞一搞。

那么就是 \(O(n+t\sqrt{n})\)

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 4000005

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 sumfenkuai(ll n) {

    ll ans=0;

    for(ll l=1,r; l<=n; l=r+1) {

        if(n/l!=0) {

            r=min(n/(n/l),n);

        } else {

            //n/l==0，意味着l>n，所有的后面的下整都是0，分成同一块

            r=n;

            break;

        }

        //phi=?

        //sum(phi)=?

        //c=n/l=n/r

        //ans=sum_d=1^n:(sum(d)*c)

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

    }

    return ans;

}

int main() {

    sieve_phi(100000+5);

    int n;

    while(cin>>n) {

        ll ans=sumfenkuai(n);

        cout<<ans<<endl;

    }

}

巴特西

洛谷 - UVA11424 - GCD - Extreme (I) - 莫比乌斯反演 - 整除分块

最新文章

热门文章