题目
传送门：QWQ
分析
呃，看到题后感觉很像上面的仪仗队。
仪仗队求的是$ 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 <bits/stdc++.h>
using namespace std;
const int maxn=1e7+3e6;
int n,pri[maxn],isp[maxn],cnt;
int phi[maxn];
int prime(){
for(int i=;i<=n;i++) isp[i]=;
for(int i=;i<=n;i++){
if(!isp[i]) continue;
pri[++cnt]=i;
for(int j=i+i;j<=n;j+=i)
isp[j]=;
}
}
void Phi(){
memset(phi,,sizeof(phi));
phi[]=;
for(int i=;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-);
}
}
}
long long sum[maxn];
int main()
{
cnt=;
long long ans=;
scanf("%d",&n);
Phi(); prime();
pri[]=;
for(int i=;i<=n;i++) sum[i]=sum[i-]+phi[i];
for(int i=;i<=cnt;i++) ans+=(long long)*sum[n/pri[i]]-; printf("%lld\n",ans);
return ;
}