BZOJ 2440 完全平方數：莫比烏斯函數與二分搜尋解法詳解

題目大意

小 X 討厭完全平方數及其正整數倍（即含平方因子的數）。給定 K，求第 K 個「不含平方因子」的正整數（無平方因子數 / Square-free numbers）。

• 測資群數 T ≤ 50
• 1 ≤ K ≤ 10⁹

核心思路：二分答案 + 莫比烏斯反演

直接求第 K 個無平方因子數困難，轉而二分答案 x，判斷 [1, x] 區間內有多少無平方因子數。

數學推導

設 μ 為莫比烏斯函數：

• μ(1) = 1
• μ(n) = (-1)ᵏ 若 n 為 k 個不同質數乘積
• μ(n) = 0 若 n 含平方因子

根據容斥原理，[1, x] 內無平方因子數個數為：

ans = Σᵢ₌₁^⌊√x⌋ μ(i) × ⌊x / i²⌋

證明略：利用 μ 函數特性過濾含平方因子的數。

演算法流程

1. 線性篩法預計算 μ(i)，i ≤ 50000（因 √(2×10⁹) ≈ 44721）
2. 對每組查詢 K，二分搜尋最小 x 使得 calc(x) ≥ K
3. calc(x) 即上述求和公式

完整程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 50005;
int mu[MAXN], primes[MAXN], cnt;
bool vis[MAXN];

// 線性篩求莫比烏斯函數
void linear_sieve() {
    mu[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        if (!vis[i]) {
            primes[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && primes[j] * i < MAXN; ++j) {
            vis[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                mu[primes[j] * i] = 0;
                break;
            } else {
                mu[primes[j] * i] = -mu[i];
            }
        }
    }
}

// 計算 [1, x] 內無平方因子數個數
ll calc(int x) {
    ll ans = 0;
    int lim = sqrt(x);
    for (int i = 1; i <= lim; ++i)
        ans += (ll)(x / (i * i)) * mu[i];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    linear_sieve();
    
    int T; cin >> T;
    while (T--) {
        int k; cin >> k;
        ll l = k, r = 2e9, ans = r;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (calc(mid) >= k) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 預處理：O(MAXN) ≈ 5×10⁴
• 單次查詢：O(√x log x) ≈ 4.5×10⁴ × 31
• 總計：T × 單次查詢，輕鬆通過時限

關鍵點總結

1. 莫比烏斯函數是處理「平方因子」問題的利器
2. 二分答案將「求第 K 個」轉化為「計數問題」
3. 線性篩同時得到質數表與 μ 函數，效率最優
4. 上界設 2×10⁹ 足夠覆蓋 K=10⁹ 的情況（第 10⁹ 個無平方因子數約 1.64×10⁹）