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

传送门
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
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("%lld\n",ans);
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

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

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡