BZOJ2818: Gcd

Portal

就直接用一下别人的题解好了。。

枚举每个素数，然后每个素数p对于答案的贡献就是（1 ~ n / p） 中有序互质对的个数而求1~m中有序互质对x，y的个数，可以令y >= x, 当y = x时，有且只有y = x = 1互质，当y > x时，确定y以后符合条件的个数x就是phiy所以有序互质对的个数为（1 ~ n/p）的欧拉函数之和乘2减1（要求的是有序互质对，乘2以后减去（1， 1）多算的一次）那么就只需要先筛出欧拉函数再求个前缀和就可以了

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #define N 10000005 #define mod 1000000007 #define INF 0x7fffffff using namespace std; typedef long long ll; typedef pair<int,int> pa; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n; ll ans,sum[N]; int p[N],not_Prime[N]={1,1},phi[N]; void getphi() { phi[1]=1; for(int i=2;i<=n;i++) { if(!not_Prime[i]) p[++p[0]]=i,phi[i]=i-1; for(int j=1;j<=p[0]&&i*p[j]<=n;j++) { not_Prime[i*p[j]]=1; if(!(i%p[j])) { phi[i*p[j]]=phi[i]*p[j]; break; } phi[i*p[j]]=phi[i]*phi[p[j]]; } } } int main() { n=read(); getphi(); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i]; for(int i=1;i<=p[0];i++) ans+=(sum[n/p[i]]<<1)-1; printf("%lld\n",ans); return 0; }