「HDU 3388」Coprime

题目大意：找出第 $k$ 个与 $n,m$ 都互质的正整数。$n,m,k \leq 10^9$

如果 $n,m$ 很小，根据 $\gcd(a,b)=\gcd(a+b,b)$ 可知，与 $n$ 互质的数形成 $\varphi(n)$ 个周期，由此得到一个 $O(lcm(n,m))$ 的算法。

设 $\sigma(n)$ 表示 $n$ 的质因子个数，在 $10^9$ 内，$\sigma(n)$ 最多为 $10$ 个左右，因此可以二分答案 $mid$，$dfs$ 选取质因子，容斥原理减去这些质因子之积的 $\leq mid$ 的倍数。

#include <cstdio>
#include <cmath>

typedef long long LL;
int p[32000], np[32000], fac[30], tot, cnt; LL res;

void prime(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!np[i]) p[++tot] = i;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
            np[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}
void previous(int n, int m) {
    cnt = 0;
    for (int i = 1; i <= tot; ++i) {
        if (n % p[i] && m % p[i]) continue;
        while (n % p[i] == 0) n /= p[i];
        while (m % p[i] == 0) m /= p[i];
        fac[++cnt] = p[i];
    }
    if (n > 1) fac[++cnt] = n;
    if (n != m && m > 1) fac[++cnt] = m;
}
void dfs(int cur, int t, LL s, LL n) {
    if (cur > cnt) {
        if (t & 1) res += n / s;
        else if (t) res -= n / s;
        return;
    }
    dfs(cur + 1, t, s, n);
    dfs(cur + 1, t + 1, s * fac[cur], n);
}

int main() {
    int T; scanf("%d", &T);
    prime(31623);
    for (int cas = 1; cas <= T; ++cas) {
        int n, m, k;
        printf("Case %d: ", cas);
        scanf("%d %d %d", &n, &m, &k);
        previous(n, m);
        LL l = 1, r = 1LL << 62;
        while (l < r) {
            LL mid = l + (r - l >> 1);
            res = 0; dfs(1, 0, 1, mid);
            if (mid - res >= k) r = mid;
            else l = mid + 1;
        }
        printf("%lld\n", l);
    }
    return 0;
}

时间复杂度 $O(T2^{\sigma(lcm(n,m))})$