gcd(数论)

题目描述

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对（x,y）有多少对？

输入

一个整数

1<=N<=1000000

输出

一个整数

样例输入

4

样例输出

4

提示

【样例解释】

(2,2),(2,4),(3,3),(4,2)

其实是做过的，我们知道，欧拉函数就是找在n以内与n互质的数，那么我们这样思考，设有一个数是x是在y范围以内与y互质的，就一定满足：

gcd(y , x) = 1

那么，如果我们同时将n乘上一个素数，如3，则就一定有：

gcd( 3*y , 3*x ) = 3

那么只要保证y*3不大于n，那么y及其y以内的数都可以满足咯，所以最后的答案就是：

其中pn为n以内质数个数，prime存的是质数。

为什么要乘2呢，因为反过来也是一种情况

为什么要加1呢？因为（n/prime[i] , n/prime[i]）也是一种情况，但是只能算一遍，且欧拉函数算的是小于n/prime[i]的

可以用前缀和

代码：



#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

int n ;

#define ll long long

const int MAXN = 1e7 + 3;

int prime[MAXN] , pn;

ll phi[MAXN];

bool vis[MAXN];

void pr(){

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

        if( !vis[i] ){

            prime[++pn] = i;

            phi[i] = i - 1;

        }

        for( int j = 1 ; j <= pn && 1ll * i * prime[j] <= n ; j ++ ){

            vis[i*prime[j]] = 1;

            if( i % prime[j] == 0 ){

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

                break;

            }

            phi[i*prime[j]] = phi[i] * ( prime[j] - 1 );

        }

    }

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

        phi[i] = phi[i] + phi[i-1];

}

int main(){

    scanf( "%d" , &n );

    pr();

    ll ans = 0;

    for( int i = 1; i <= pn ; i ++ ){

        ans = ans + phi[n/prime[i]] * 2 + 1;

    }

    printf( "%lld" , ans );

    return 0;

}

---------------------

作者：BIT_jzx

原文：https://blog.csdn.net/weixin_43823476/article/details/89077146

巴特西

gcd(数论)

最新文章

热门文章