首页 > 代码库 > POJ 2773 容斥原理
POJ 2773 容斥原理
链接：
http://www.cnblogs.com/MashiroSky/p/5913989.html
题意：
给出两个数m,k，要求求出从1开始与m互质的第k个数。
题解：
二分一个答案mid，容斥统计出在区间[1，mid]中是m的质因子的倍数的数的个数ans，然后我们可以用mid-ans得到区间中有多少个与m互质的数，不断二分下去，直到得出答案。
代码：
31 ll n, k;32 ll factor[MAXN], sz;33 ll sum, mid;34 35 void prime_factor(ll n) {36 sz = 0;37 for (ll i = 2; i*i <= n; i++) if (n%i == 0) {38 factor[sz++] = i;39 while (n%i == 0) n /= i;40 }41 if (n > 1) factor[sz++] = n;42 }43 44 void dfs(ll id, ll step, ll num) {45 if (id == sz) {46 if (step != 0) {47 if (step & 1) sum += mid / num;48 else sum -= mid / num;49 }50 return;51 }52 dfs(id + 1, step, num);53 if (num*factor[id] <= mid)54 dfs(id + 1, step + 1, num*factor[id]);55 }56 57 int main() {58 while (cin >> n >> k) {59 prime_factor(n);60 ll l = k, r = 1e18, ans = l;61 while (l <= r) {62 mid = (l + r) / 2;63 sum = 0;64 dfs(0, 0, 1);65 if (mid - sum >= k) r = mid - 1, ans = mid;66 else l = mid + 1;67 }68 cout << ans << endl;69 }70 return 0;71 }
POJ 2773 容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。