首页 > 代码库 > 省赛i题/求1~n内所有数对(x,y),满足最大公约数是质数的对数
省赛i题/求1~n内所有数对(x,y),满足最大公约数是质数的对数
求1~n内所有数对(x,y),gcd(x,y)=质数,的对数。
思路:用f[n]求出,含n的对数,最后用sum【n】求和。
对于gcd(x,y)=a(设x<=y,a是质数),则必有gcd(x/a,y/a)=1;所以我只要枚举i(设i=y/a),再枚举所有质数
思路:用f[n]求出,含n的对数,最后用sum【n】求和。
对于gcd(x,y)=a(设x<=y,a是质数),则必有gcd(x/a,y/a)=1;所以我只要枚举i(设i=y/a),再枚举所有质数
他们乘积的f[i*a]值包括i的欧拉函数值。时间复杂度(n*质数个数)
#include<iostream> #include<cstring> using namespace std; const int maxx=100010; int mindiv[maxx+5],phi[maxx+5]; void genphi() //求出1~n内所有数的欧拉函数值 { for(int i=1; i<=maxx; i++) { mindiv[i]=i; } for(int i=2; i*i<=maxx; i++) //筛法 { if(mindiv[i]==i) { for(int j=i*i; j<=maxx; j+=i) { mindiv[j]=i; } } } phi[1]=1; for(int i=2; i<=maxx; i++) { phi[i]=phi[i/mindiv[i]]; if((i/mindiv[i])%mindiv[i]==0) { phi[i]*=mindiv[i]; } else { phi[i]*=mindiv[i]-1; } } } int pri[maxx+5]; int nump=0; //素数个数 int pp[maxx+5]; //存素数 void getp() { for(int i=2;i<=maxx;i++) { while(i<=maxx&&pri[i])i++; pp[nump++]=i; for(int j=i*2;j<=maxx;j=j+i) pri[j]=1; } } long long f[maxx+5]; long long sum[maxx+5]; int main() { getp(); genphi(); for(int i=1;i<=maxx;i++) // 枚举每个i,i=y/pp[j]() { for(int j=0;j<nump&&i*pp[j]<=maxx;j++) //枚举所有质数 { if(i!=1) //(a,b)(b,a)算俩次。 f[i*pp[j]]+=phi[i]*2; else f[i*pp[j]]+=phi[i]; } } long long tsum=0; for(int i=1;i<=maxx;i++) { tsum+=f[i]; sum[i]=tsum; } int n; while(cin>>n) { cout<<sum[n]<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。