acwing 220. 最大公约数

@[toc]

题目：

给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
GCD(x,y)即求x，y的最大公约数。

题解：

列出公式推导即可

代码：

#include<bits/stdc++.h>
#define MAXN 10000011
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
bool vis[MAXN];
int pri[MAXN/10],cnt=0;
ll phi[MAXN];
void solve()
{
    phi[1]=1;vis[1]=1;
    for(ll i=2;i<MAXN;++i)
    {
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
        for(ll j=1;j<=cnt&&i*pri[j]<MAXN;++j)
        {
            ll v=i*pri[j];
            vis[v]=1;
            if(i%pri[j]==0)
            {
                phi[v]=phi[i]*pri[j];break;
            }
            phi[v]=phi[i]*phi[pri[j]];
        }
    }
    for(ll i=1;i<MAXN;++i)phi[i]+=phi[i-1];
}
int main()
{
    solve();
    ll n=read(),ans=0;
    for(ll i=1;i<=cnt&&pri[i]<=n;++i)ans+=(2*phi[n/pri[i]]-1);
    printf("%lld",ans);
    return 0;
}