bzoj2818 gcd 欧拉函数（前缀和）

莱昂哈德 欧拉

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

4
Sample Output

4

这道题是比较水的一道数论题……
如果说两人数的gcd为质数，那么同时除以这个质数，gcd就为1，gcd为1的话我们就能明白这两数一定互质，那么我们就枚举n以内的质数，对每一个质数求出n/p（p为此质数）以内所有的phi（欧拉函数）值之和，对于质数和欧拉函数我们用线性筛来求.注意本题求的是对数，所以反过来也可以，要每次枚举的答案*2-1,-1是因为（1,1）被多计算的一次；

#include<stdio.h>
const int maxn=10000005;
typedef long long dnt;
int n,pr[1000005],k,phi[maxn],tot;
dnt sum[maxn],ans;
bool mark[maxn];
inline void Linear_sieve(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!mark[i]) pr[++tot]=i,phi[i]=i-1;
        for(int j=1;pr[j]*i<=n&&j<=tot;j++){
            k=i*pr[j];
            mark[k]=true;
            if(i%pr[j]==0) {phi[k]=phi[i]*pr[j];break;}
            else phi[k]=phi[i]*(pr[j]-1);
        }
    }
}
int main(){
    scanf("%d",&n);
    Linear_sieve();
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
    for(int i=1;i<=tot;i++)
     ans+=sum[n/pr[i]]*2-1;
    printf("%lld",ans);
}

                           ----数学是艺术