问题描述:

给定整数$N$,求$1<=x,y<=N$且$gcd(x, y)$为素数的数对$(x, y)$有多少对

输入:

一个数$N$($1<=N<=10^7$)

输出:

满足条件的对数

思路:

这题有莫比乌斯反演的做法。。。其实不用反演的做法感觉更好想。

看完数据范围,做法应该就是在$O(n)$左右的。我们可以先筛出范围内的素数,然后可以暴力对每个素数$pri[i]$计算范围内$gcd(x, y)=pri[i]$的对数。

范围内$gcd(x, y)=pri[i]$的对数也就相当于在$1<=x,y<= N/pri[i]$范围内互素的个数。在某个范围内互素的个数就是欧拉函数的前缀和*2+1,因此这个我们可以$O(1)$求出。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 10000007
#define LL long long
using namespace std;

int n, cnt, pri[MAXN];
LL ans, phi[MAXN];
bool vis[MAXN];

int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        if(!vis[i]) pri[++cnt]=i, phi[i]=i-1;
        for(int j=1; j<=cnt && i*pri[j]<=n; j++)
        {
            vis[pri[j]*i]=1;
            if(i%pri[j]==0) {phi[i*pri[j]]=pri[j]*phi[i]; break;}
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
    for(int i=2; i<=n; i++) phi[i]+=phi[i-1];
    for(int i=1; i<=cnt; i++) ans+=phi[n/pri[i]]*2+1;
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注