POJ 2773 Happy 2006：互質數第 K 個——質因子分解+容斥+二分

問題

給定 m（≤ 10⁶），求第 k（≤ 10⁸）個與 m 互質的正整數。

核心公式

設 m 的不同質因子為 p₁…p_r。
≤ x 且與 m 不互質的數 = 容斥原理計算：
f(x) = Σ (−1)^|S|+1 ⌊x / ∏_i∈S p_i⌋。
與 m 互質的數 = x − f(x)。
二分最小 x 使 x − f(x) ≥ k。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector prime;
void factor(int m) {
    for (int i = 2; i * i <= m; ++i)
        if (m % i == 0) { prime.push_back(i); while (m % i == 0) m /= i; }
    if (m > 1) prime.push_back(m);
}
ll countNotCoprime(ll x) {
    ll sum = 0; int r = prime.size();
    for (int mask = 1; mask < (1<>i & 1) {
            prod *= prime[i]; ++bits;
        }
        sum += (bits & 1 ? 1 : -1) * (x / prod);
    }
    return sum;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int m; ll k;
    while (cin >> m >> k) {
        prime.clear(); factor(m);
        ll lo = 1, hi = 1e18, ans = hi;
        while (lo <= hi) {
            ll mid = (lo + hi) >> 1;
            if (mid - countNotCoprime(mid) >= k) { ans = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

替代方法：歐拉定理周期性

gcd(km+i, m) = gcd(i, m) → 互質數對 m 取模週期為 m。
預處理 1…m 中互質數列表，直接計算第 k 個。
複雜度 O(m log m) 預處理，適合 m ≤ 10⁶、單次查詢。

複雜度

質因子分解 O(√m)；容斥 2^r（r ≤ 7）；二分 log(10¹⁸) ≈ 60。總體極快。