洛谷 P2568 GCD

https://www.luogu.org/problemnew/show/P2568#sub

最喜欢题面简洁的题目了。

本题为求两个数的gcd是素数，那么我们将x和y拆一下，

假设p为$gcd(x,y)$,且p是一个素数，$x=a \times p , y = b \times p $。

然而要满足p的条件的话，a和b一定是互质的，满足$0 \le a,b \le \frac{n}{p} $

这样的话我们可以枚举这个质数p，将小于$\frac{n}{p}$的数，以及与它互质的数加起来。

互质的数的个数自然想到了欧拉函数，优化想加的话显然前缀和(我就琢磨了半天)

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

#define LL long long

int n;

int prime[],tot;

bool vis[];

LL phi[],ans;

void get_phi()

{

    phi[]=;

    for(int i=;i<=n;i++)

    {

        if(!vis[i])prime[++tot]=i,phi[i]=i-;

        for(int j=;j<=tot&&prime[j]*i<=n;j++)

        {

            vis[prime[j]*i]=;

            if(i%prime[j]==)

            {

                phi[i*prime[j]]=phi[i]*prime[j];

                break;

            }

            else phi[i*prime[j]]=phi[i]*phi[prime[j]];

        }

    }

    for(int i=;i<=n;i++)phi[i]=phi[i-]+phi[i];

}

int main()

{

    scanf("%d",&n);

    get_phi();

    for(int i=;i<=tot;i++)ans+=phi[n/prime[i]];

    printf("%lld",ans*+tot);
　　//乘2的原因就不多说了(x,y)和(y,x)啊。
　　　之所以再加一个tot是因为我的phi数组定义的phi[1]=0.

}

巴特西

洛谷 P2568 GCD

最新文章

热门文章