题目

 

 

分析

呃，看到题后感觉很像上面的仪仗队。

仪仗队求的是$ gcd(a,b)=1 $

本题求的是$ gcd(a,b)=m $ 其中m是质数

把 $ gcd(a,b)=1 $ 变形成 $ gcd(a,b)*m=m $

然后在n的范围内枚举一下，使 $ gcd(a,b)*m <= n $

再像仪仗队那样用欧拉函数搞一搞。

没了。

 

 

代码

 

#include 
      
       using namespace std;const int maxn=1e7+3e6;int n,pri[maxn],isp[maxn],cnt;int phi[maxn];int prime(){    for(int i=1;i<=n;i++) isp[i]=1;    for(int i=2;i<=n;i++){        if(!isp[i]) continue;        pri[++cnt]=i;        for(int j=i+i;j<=n;j+=i)            isp[j]=0;    }}void Phi(){    memset(phi,0,sizeof(phi));    phi[1]=1;    for(int i=2;i<=n;i++){        if(phi[i]) continue;        for(int j=i;j<=n;j+=i){            if(!phi[j]) phi[j]=j;            phi[j]=phi[j]/i*(i-1);        }    }}long long sum[maxn]; int main(){    cnt=0;    long long ans=0;    scanf("%d",&n);    Phi(); prime();    pri[0]=1;    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];    for(int i=1;i<=cnt;i++) ans+=(long long)2*sum[n/pri[i]]-1;        printf("%lld\n",ans);    return 0;}