HDU 3388 Coprime：二分 + 容斥原理求第 k 個互質數

題目

給定 n, m, k，求第 k 個與 n 和 m 都互質的正整數。n,m ≤ 10^5, k ≤ 10^9。

解法

設 f(x) = [1,x] 中與 n,m 互質的數的個數。f(x) 隨 x 遞增，二分查找最小 x 使 f(x) ≥ k。
f(x) = x - g(x)，其中 g(x) = 與 n 或 m 不互質的數個數。由容斥原理，g(x) 可通過 n,m 的質因子聯集計算：對所有非空子集，符號交替加減 x / (質因子乘積)。預處理 n,m 的質因子聯集，DFS 實現容斥。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXP = 100000;
vector pf; // n,m 的質因子聯集
bool vis[MAXP+5];

void getPrimeFactors(int x) {
    for (int i = 2; i*i <= x; i++)
        if (x%i==0 && !vis[i]) { pf.push_back(i); vis[i]=1; while(x%i==0) x/=i; }
    if (x>1 && !vis[x]) { pf.push_back(x); vis[x]=1; }
}

ll dfs(int idx, ll limit) {
    ll res = 0;
    for (int i = idx; i < (int)pf.size(); i++) {
        ll p = pf[i];
        res += limit/p - dfs(i+1, limit/p);
    }
    return res;
}

ll countCoprime(ll x) { return x - dfs(0, x); }

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        pf.clear(); memset(vis, 0, sizeof(vis));
        getPrimeFactors(n); getPrimeFactors(m);
        ll l = 1, r = 1e18, ans = r;
        while (l <= r) {
            ll mid = (l+r)>>1;
            if (countCoprime(mid) >= k) ans = mid, r = mid-1;
            else l = mid+1;
        }
        printf("Case %d: %lld\n", cas, ans);
    }
    return 0;
}