poj1796专题

NYOJ762+POJ1796 第k个互质数(容斥原理+二分)

描述 两个数的a,b的gcd为1,即a,b互质,现在给你一个数m,你知道与它互质的第k个数是多少吗?与m互质的数按照升序排列。 输入 输入m ,k (1<=m<=1000000;1<=k<=100000000) 输出 输出第k个数。 样例输入 10 110 210 3 样例输出 137 思路 题意要求出与m互质的第k个数,首先肯定不能暴力,要用容