首页 > 代码库 > NYOJ_762:第k个互质数
NYOJ_762:第k个互质数
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=762
直接给代码好了,容斥原理具体看《组合数学》
#include<bits/stdc++.h> using namespace std; typedef long long LL; vector<int> a; //存储n所有质因子 //不爆int情况下,大概最多10个左右 int b[1010]; void getfac(int x) { for(int i=2;i*i<=x;i++) if(x%i==0) { a.push_back(i); while(x%i==0) x/=i; } if(x>1) a.push_back(x); } int cal(int x) //由容斥原理计算1~x中有多少与n互质的自然数 { int g=0,ret=x; b[++g]=1; //由以下的二重for循环可以做到枚举组合,共2^(a.size())个组合 for(int i=0;i<a.size();i++) { int t=g; for(int j=1;j<=g;j++) b[++t]=-b[j]*a[i],ret+=x/b[t]; g=t; } return ret; } int work(int n,int k) //二分查找 { int l=0,r=2e9; //cal(l)<k,cal(r)>=k while(r-l>1) //当r-l=1时,结束循环,此时cal(r)=k { int mid=l+(r-l)/2; if(cal(mid)<k) l=mid; else r=mid; } return r; } int main() { int n,k; while(cin>>n>>k) { a.clear(); getfac(n); printf("%d\n",work(n,k)); } }
NYOJ_762:第k个互质数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。