题意：

有一张表 f[x][y]，共x*y个数

现在要删去所有的 f[x*k][y*k] ,k>1

最后还剩多少个数

 

题意转化：有多少个二元组（x，y）满足 gcd（x，y）=1

若x<y，则 f[][y]=phi(y)

所以 ans= （2* Σ phi（y））+1   y∈[2,n]

加的1为（1,1）

线性筛出欧拉函数求和即可

#include
     
      #define N 50001using namespace std;bool v[N];int phi[N],cnt,p[N];int main(){    for(int i=2;i
      
       =N) break;            v[i*p[j]]=true;            if(i%p[j]) phi[i*p[j]]=(p[j]-1)*phi[i];            else            {                phi[i*p[j]]=phi[i]*p[j];                break;            }        }    }    for(int i=2;i