[BZOJ2818]GCD

[BZOJ2818]GCD

BZOJ
luogu
求$$sum_{i=1}^nsum_{j=1}n[gcd(i,j)是质数]$$
考虑枚举n以内的质数k((10^7)内大概70万个)
那么每个质数k的贡献$$sum_{i=1}^nsum_{j=1}n[gcd(i,j)=k]$$

[=sum_{i=1}^{lfloorfrac{n}{k} floor}sum_{j=1}^{lfloorfrac{n}{k} floor}[gcd(i,j)=1] ]

[=2sum_{i=2}^{lfloorfrac{n}{k} floor}phi(i)+1 ]

所以相当于求$$sum_k[2sum_{i=2}^{lfloorfrac{n}{k} floor}phi(i)+1]$$
其中k是小于等于n的质数
可以线性筛素数,筛(phi)之后暴力求解,复杂度大概是个什么鬼调和级数?
但是发现(phi)前缀和一下就可以线性了(实测并没有快...)
听说还有根号做法?

#define ll long long
#include<bits/stdc++.h>
using namespace std;
const int _=1e7+5;
int n,cnt;
int p[700000];
ll ans,phi[_];
bool vis[_];
int main(){
    cin>>n;phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])p[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&p[j]*i<=n;j++){
            int v=p[j]*i;vis[v]=1;
            if(i%p[j]==0){phi[v]=p[j]*phi[i];break;}
            phi[v]=(p[j]-1)*phi[i];
        }
    }
	for(int i=3;i<=n>>1;i++)phi[i]+=phi[i-1];
    ans=cnt;
    for(int i=1;i<=cnt;i++)
		if(n/p[i]>=2)ans+=phi[n/p[i]]<<1;
    cout<<ans<<endl;
    return 0;
}