首页 > 代码库 > BZOJ2818 Gcd 欧拉函数
BZOJ2818 Gcd 欧拉函数
题意：给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.
题解：我们枚举素数p，后面的过程和BZOJ2705一样，不同的是我们限制x>=y，假定得到的答案是ans，那么实际上答案是2*ans-1（加上x<=y，x==y重复计算了）
#include <cmath>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=10000000+2;ll phi[MAXN],prime[MAXN/10],cnt,N,ans;bool flag[MAXN];void Euler(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(!flag[i]) prime[++cnt]=i,phi[i]=i-1; for(int j=1;j<=cnt && prime[j]*i<=n;j++){ flag[prime[j]*i]=1; if(!(i%prime[j])){ phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } }}int main(){ cin >> N; Euler(N); for(int i=2;i<=N;i++) phi[i]+=phi[i-1]; for(int i=1;i<=cnt;i++) ans+=2*phi[N/prime[i]]-1; cout << ans << endl; return 0;}
BZOJ2818 Gcd 欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。