Luogu P2568 GCD

题目链接：Click here

Solution:

我们尝试着转化一下式子

[sum_{pin pri} sum_{i=1}^n sum_{j=1}^n [gcd(i,j)=p]\ sum_{pin pri} sum_{i=1}^{lfloor {nover p} floor} sum_{j=1}^{lfloor {nover p} floor} [gcd(i,j)=1]\ ]

后面一部分有些眼熟(要素察觉

[sum_{pin pri} sum_{i=1}^{lfloor {nover p} floor} sum_{j=1}^{lfloor {nover p} floor} sum_{d|i,d|j} mu(d)\ sum_{pin pri} sum_{d=1}^{lfloor {nover p} floor} mu(d) {lfloor {nover pd} floor}^2\ T=dp\ sum_{T=1}^n {lfloor {nover T} floor}^2sum_{p|T,pin pri} mu({Tover p}) ]

我们令(f(T)=sum_{p|T,pin pri} mu({Tover p}))，考虑如何线筛

当(Tin pri)，(f(T)=1)是十分显然的，考虑(f(T imes p),pin pri)

经过简单推导可发现(p|T)时，(f(T imes p)=mu(T))，否则(f(T imes p)=-f(T)+mu(T))

那么我们便可以愉快的数论分块了！时间复杂度(O(sqrt n+n))

正解phi?看到gcd就莫反的我是不是已经没救了

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+11;
bool vis[N];
int n,cnt,ans,p[N],u[N],f[N];
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void prepare(){
    u[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++cnt]=i,u[i]=-1,f[i]=1;
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                f[i*p[j]]=u[i];
                break;
            }
            u[i*p[j]]=-u[i];
            f[i*p[j]]=-f[i]+u[i];
        }
    }
    for(int i=1;i<=n;i++) f[i]+=f[i-1];
}
signed main(){
    n=read();
    prepare();
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        int v=n/i;v=v*v;
        ans+=(f[j]-f[i-1])*v;
    }printf("%lld
",ans);
    return 0;
}