题目大意

给定整数$n$，求$1\leqslant x,y\leqslant n$且$gcd(x,y)$为素数的数对$(x,y)$有多少对

数据范围

$1\leqslant n\leqslant 10^7$

题解

在每个质数$p$中，对答案的贡献是$[1..\left\lfloor\frac{n}{p}\right\rfloor]$中互质的数对

那么容易发现，这就是欧拉函数！

这么一个区间的有序互质数对数量就是$ans=\sum^{\left\lfloor\frac{n}{p}\right\rfloor}_{i=1}\varphi(i)$，然后总数就是$ans\times 2-1$

然后对应每一个质数，都算出其答案，最后加起来输出就行了

程序

#include<cstdio>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
#define maxn 10005000
using namespace std;

int phi[maxn],prime[maxn],flag[maxn];
ll sum[maxn],ans;
int n,tot;

inline void getphi(){
    phi[1]=1;
    For(i,2,n){
        if (!flag[i]){prime[++tot]=i;phi[i]=i-1;}
        For(j,1,tot){
            if (i*prime[j]>n) break;
            flag[i*prime[j]]=1;
            if (!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main(){
    scanf("%d",&n);
    getphi();
    For(i,1,n) sum[i]=sum[i-1]+phi[i];
    For(i,1,tot) ans+=sum[(ll)n/prime[i]]*2-1;
    printf("%lld\n",ans);
    return 0;
}