給定 m (≤1e6) 和 K (≤1e8)，求第 K 個與 m 互質的正整數。
設 f(x) = [1,x] 中與 m 互質的數個數。f(x) 單調遞增。二分最小 x 使 f(x) ≥ K，即為答案。
f(x) = x - Σ_{p|m} x/p + Σ_{p
m 的質因子數 ≤ 7（因 2*3*5*7*11*13*17>1e6），子集枚舉 2^7=128 極快。
vector primes; // m 的質因子
LL calc(LL x) {
LL res=0;
for (int mask=1; mask<(1<>i&1) prod*=primes[i];
if (bits&1) res += x/prod;
else res -= x/prod;
}
return x - res; // 互質數個數
}
int main() {
LL m, K;
while (cin>>m>>K) {
primes.clear();
LL tm=m;
for (LL i=2;i*i<=tm;i++) if (tm%i==0) {
primes.push_back(i);
while (tm%i==0) tm/=i;
}
if (tm>1) primes.push_back(tm);
LL l=1, r=1LL<<60, ans=-1;
while (l<=r) {
LL mid=(l+r)>>1;
if (calc(mid)>=K) { ans=mid; r=mid-1; }
else l=mid+1;
}
printf("%lld\n", ans);
}
return 0;
}
O(√m)。1LL<<60 足夠大（K≤1e8, m≥1 時答案 < 2e8）。__builtin_popcount 計算集合大小決定符號。POJ 2773 是「二分答案 + 容斥計數」的經典組合。關鍵在於將「第 K 個滿足性質的數」轉化為「計數函數單調性」，並利用質因子數少的特性高效實現容斥。模板極其通用，適用於各類「第 K 個互質/不被整除」問題。
