前言
耻辱，我这个OI界的耻辱！
题目描述
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.
输入格式
一个整数N
输出格式
答案
输入输出样例
输入
4
输出
4
说明/提示
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
分析
刚学（抄）完莫比乌斯反演做完P2522和P3455的我刚看到这个题第一反应竟然是
这不是个莫比乌斯反演的板子题吗 <----zz言论
看我切了他 <----zz行为
瞄了一眼算法标签额。。。嗯？？？？？欧拉函数？？？前缀和？？？
于是老老实实想出了正常点的解法，写个博客记录一下自己的zz行为（免得今年csp上写一个莫比乌斯反演出来
首先$\gcd (a,b)$为素数，那么$a$与$b$肯定只有1与$\gcd (a,b)$这两个公约数，
不妨考虑$\gcd (a,b)=1$,然后$a$和$b$同时乘上一个素数即可
考虑每个数的贡献。为了防止算重复，每个数只计算比它小的数。
根据欧拉函数的定义可知，对于一个数$a$，有$\varphi (a)$个比它小且与它互质的数
这$\varphi (a)$个数每个数乘上一个素数$p$,与$ap$的$gcd$都是素数$p$，都会对答案造成贡献
而且只要$ap<=n$，其它数都小于等于$n$。
所以对于每个数$a$，枚举最大的素数$p$满足$ap<=n$,如果$p$是第$k$个质数,$\varphi (a)k$就是$a$的贡献。
从小到大枚举$a$，那么对应的$p$肯定从大到小递减，具有单调性，可以$O(n)$计算。
另外，还要每个素数与自己取$gcd$的情况也要计算。
Code
#include<cstdio>
int n,p[],phi[],unp[];
long long ans;
void prework()
{
unp[]=phi[]=;
for(int i=;i<=n;i++)
{
if(!unp[i])p[++p[]]=i,phi[i]=i-;
for(int j=;1ll*p[j]*i<=n;j++)
{
unp[p[j]*i]=;
if(i%p[j])phi[p[j]*i]=(p[j]-)*phi[i];
else {phi[p[j]*i]=p[j]*phi[i];break;}
}
}
}
int main()
{
scanf("%d",&n);prework();
for(int i=,j=p[];i<=n;i++)
{
while(1ll*p[j]*i>n&&j)j--;
ans+=1ll*phi[i]*j;
}
printf("%lld\n",ans*+p[]);
}