P2568 GCD
#$Description$
给定$n$，求$1<=x,y<=n$满足$gcd(x,y)=p$(其中$p$为质数)的$(x,y)$有多少对
#$Solution$
乍一看是莫比乌斯反演，~~虽然我不会莫比乌斯反演~~
其实这道题是简单的筛法+欧拉函数
$ans=sumlimits_{i=1}^nsumlimits_{j=1}^n[gcd(i,j)==p]$
$gcd$常用技巧
$=sumlimits_{pin prime}sumlimits_{i=1}^{lfloor frac{n}{p}
floor}sumlimits_{j=1}^{lfloor frac{n}{p}
floor}[gcd(i,j)==1]$
因为$i,j$是等效的，所以只用将$j$枚举到$i$即可，保证$j
#include
#include
#define maxn 10000010
#define re register
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll ans;
int n,is_not_prime[maxn],prime[maxn],pcnt,phi[maxn];
void pre()
{
is_not_prime[1]=1;
phi[1]=1;
for(int i=1;i<=n;++i)
{
if(!is_not_prime[i])
{
prime[++pcnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=pcnt;++j)
{
if(i*prime[j]>n) break;
is_not_prime[i*prime[j]]=1;
if(i % prime[j]==0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
int main()
{
n=read();
pre();
for(re int i=1;i<=pcnt;++i)
{
for(re int j=1;j<=n/prime[i];++j)
{
ans+=2*phi[j];
}
ans--;
}
//for(re int i=1;i<=n;++i) printf("%d ",phi[i]);
printf("%lld
",ans);
return 0;
}
```