BZOJ 2440 完全平方數：二分答案 + 莫比烏斯反演容斥計數

題目大意

**完全平方數** = 含有平方因子的數（即 ∃ p² | x, p>1）。
求第 K 個**非完全平方數**（即無平方因子數 / square-free numbers）。
多測試用例，K ≤ 10⁹。

核心轉化

• 設 f(x) = [1, x] 範圍內**非完全平方數**個數。
• 答案 = 最小 x 使 f(x) ≥ K → **二分答案**。
• f(x) = x - g(x)，其中 g(x) = 完全平方數個數。

莫比烏斯函數容斥計算 g(x)

完全平方數 = 能被某個 p² 整除的數。
容斥原理：
g(x) = ∑_{i=2}^{√x} μ(i) * ⌊x / i²⌋ (注意符號)

實際上：
非完全平方數個數 = ∑_{i=1}^{√x} μ(i) * ⌊x / i²⌋
其中 μ(1)=1，μ(i) 為莫比烏斯函數。

莫比烏斯函數線性篩預處理

const int MAXM = 100000; // √(2e16) ≈ 1.4e8，但 K≤1e9 實際 x≤2e9，√x≤44721，1e5 足夠
int mu[MAXM];
vector primes;
bool vis[MAXM];

void mobius_sieve() {
    mu[1] = 1;
    for (int i = 2; i < MAXM; ++i) {
        if (!vis[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if (i * p >= MAXM) break;
            vis[i * p] = true;
            if (i % p == 0) { mu[i * p] = 0; break; }
            else mu[i * p] = -mu[i];
        }
    }
}

計數函數與二分

long long countSquareFree(long long x) {
    long long res = 0;
    for (long long i = 1; i * i <= x; ++i)
        res += mu[i] * (x / (i * i));
    return res;
}

long long kthSquareFree(long long K) {
    long long L = 1, R = 2e16; // 足夠大上界
    while (L <= R) {
        long long mid = (L + R) >> 1;
        if (countSquareFree(mid) < K) L = mid + 1;
        else R = mid - 1;
    }
    return L;
}

完整代碼

#include 
using namespace std;

const int MAXM = 100000;
int mu[MAXM];
bool vis[MAXM];
vector primes;

void init_mu() {
    mu[1] = 1;
    for (int i = 2; i < MAXM; ++i) {
        if (!vis[i]) { primes.push_back(i); mu[i] = -1; }
        for (int p : primes) {
            if (i * p >= MAXM) break;
            vis[i * p] = true;
            if (i % p == 0) { mu[i * p] = 0; break; }
            else mu[i * p] = -mu[i];
        }
    }
}

long long cnt_sf(long long x) {
    long long res = 0;
    for (long long i = 1; i * i <= x; ++i)
        res += mu[i] * (x / (i * i));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init_mu();
    int T; cin >> T;
    while (T--) {
        long long K; cin >> K;
        long long L = 1, R = 2e16;
        while (L <= R) {
            long long mid = (L + R) >> 1;
            if (cnt_sf(mid) < K) L = mid + 1;
            else R = mid - 1;
        }
        cout << L << '\n';
    }
    return 0;
}

複雜度分析

• 莫比烏斯篩：O(MAXM) ≈ 10⁵。
• 單次計數：O(√x) ≤ 4.5×10⁴ (x ~ 2×10⁹)。
• 二分：O(log 2e16) ≈ 55 次。
• 單測試用例：55 × 4.5e4 ≈ 2.5e6 操作，多測試用例 (T≤50) 仍在 1 秒內。

關鍵細節

1. 上界設置：R = 2e16 覆蓋 K=1e9 情況 (實際第 1e9 個 square-free 約 1.6e9)。
2. 莫比烏斯定義：μ(1)=1，質數 -1，含平方因子 0，其餘 (-1)^k。
3. 符號驗證：μ(2)=-1 → 減去 x/4 (4 的倍數)；μ(6)=1 → 加回 x/36 (被 4 和 9 重減的)。
4. 長整型：x/(i*i) 中 i*i 可能溢出 int，用 long long。

總結

BZOJ 2440 是 **莫比烏斯反演 + 二分答案** 的經典模板題。
核心鏈路：無平方因子計數 = ∑ μ(i) ⌊x/i²⌋ → 二分求第 K 個。
掌握線性篩求 μ、容斥符號規律、二分邊界設置，即可秒殺同類問題。