BZOJ 2818: Gcd区间内最大公约数为素数的对数(欧拉函数的应用)

发布时间：2020-12-13 21:09:26 所属栏目：PHP教程来源：网络整理

导读：传送门 2818: Gcd Time Limit: 10 Sec Memory Limit: 256 MB Submit: 3649 Solved: 1605 [Submit][Status][Discuss] Description 给定整数N，求1=x,y=N且Gcd(x,y)为素数的数对(x,y)有多少对. Input 1个整数N Output 如题 Sample Input 4 Sample Output 4 HI

传送门
2818: Gcd

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3649 Solved: 1605
[Submit][Status][Discuss]
Description

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

Input

1个整数N

Output

如题

Sample Input

Sample Output

4
HINT

hint

对样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

Source

湖北省队互测

解题思路：
这个题是让求的<=n的GCD(x,y)==素数的个数(2,4)和(4,2)认为是不1样的，那末我们可以想到枚举每个素数，让其GCD(x,y)=p,那末我们可以想到在[1,y/p]内与y/p互素的个数（在这里默许 y>x），那末我们就是求1个欧拉函数值，那末我们将其扩大到1-n区间内，就是求[1,n/p]的欧拉函数值，但是我们需要求的是sigmaEualr(n/p)的前缀和，由于y是从1-n之间取的，所以对数就是sum[n/p]*2⑴,由于是对数，而且还有重复的情况（本身是素数的情况）

具体详见代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef long long LL;
const LL MAXN = 1e7+5;
bool prime[MAXN];///标记数组是否是素数
LL phi[MAXN];///欧拉函数值，i的欧拉函数值=phi[i]
LL p[MAXN];///素因子的值
LL cnt = 0;
void get_Phi()///筛法求欧拉函数
{
    cnt = 0;
    memset(prime,true,sizeof(prime));
    phi[1] = 1;
    for(LL i=2; i<MAXN; i++)///线性筛法
    {
        if(prime[i])///素数
        {
            p[cnt++] = i;
            phi[i] = i-1;///素数的欧拉函数值是素数 - 1
        }
        for(LL j=0; j<cnt; j++)
        {
            if(i*p[j] > MAXN)
                break;
            prime[i*p[j]] = false;///素数的倍数，所以i*p[j]不是素数
            if(i%p[j] == 0)///性质：i mod p == 0,那末 phi(i * p) == p * phi(i)
            {
                phi[i*p[j]] = p[j] * phi[i];
                break;
            }
            else
                phi[i*p[j]] = (p[j]-1) * phi[i];///i mod p != 0,那末 phi(i * p) == phi(i) * (p⑴)
        }
    }
}
LL sum[MAXN];///前缀和
void get_sum()
{
    memset(sum,0,sizeof(sum));
    for(LL i=1; i<MAXN; i++)
        sum[i] = sum[i-1]+phi[i];
}
int main()
{
    get_Phi();
    get_sum();
    LL n;
    while(~scanf("%lld",&n))
    {
        LL ans = 0;
        for(LL i=0; i<cnt&&p[i]<=n; i++)
        {
            ans = ans+sum[n/p[i]]*2-1;
        }
        printf("%lldn",ans);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

BZOJ 2818: Gcd区间内最大公约数 为素数的对数(欧拉函数的应用)

BZOJ 2818: Gcd区间内最大公约数为素数的对数(欧拉函数的应用)