UVA 11014 Make a Crystal：容斥原理與勒讓德符號應用

題目轉述

給定 N × N × N 整數格點立方體，求最多能選多少個點，使得任意兩點 P, Q 與原點 O 不共線（即向量 OP、OQ 不共線）。

數學建模

• 點 (x,y,z) 與原點共線 ⇔ 存在 k>1 使 (x,y,z) = k·(x',y',z')。
• 等價於：選取的點互質（gcd(x,y,z)=1），且不成比例。
• 總點數（含原點）：(N+1)³，扣除原點後為 f(1) = (N+1)³ - 1。
• 若點的三個座標公倍數為 d>1，則該點與原點連線上至少還有 (d-1) 個整點，違反條件。

容斥原理推導

設 g(d) 為三個座標皆為 d 的倍數的點數（不含原點）：

g(d) = (⌊N/d⌋·2 + 1)³ - 1（因座標範圍 [-N,N]，步長 d）

答案 = ∑_{d=1}^{N} μ(d) · g(d)，其中 μ 為莫比烏斯函數。

等價於：質因數個數為奇數的 d 扣除，偶數加回（容斥）。

算法步驟

1. 線性篩預計算 μ(d) 至 200,000（N ≤ 100,000）。
2. 對每個測試案例，枚舉 d=1..N，累加 μ(d) * g(d)。
3. μ(d)=0（含平方因子）時跳過。

C++ 實作

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 200000;

int mu[MAXN+1], primes[MAXN], pcnt;
bool vis[MAXN+1];

void linearSieve() {
    mu[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        if (!vis[i]) { primes[pcnt++] = i; mu[i] = -1; }
        for (int j = 0; j < pcnt && i*primes[j] <= MAXN; ++j) {
            vis[i*primes[j]] = true;
            if (i % primes[j] == 0) { mu[i*primes[j]] = 0; break; }
            else mu[i*primes[j]] = -mu[i];
        }
    }
}

int64 g(int64 n, int64 d) {
    int64 k = n / d;
    int64 cnt = 2*k + 1; // -k..k 共 2k+1 個整數
    return cnt*cnt*cnt - 1; // 扣除原點
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    linearSieve();
    int64 n; int tc = 0;
    while (cin >> n && n) {
        int64 ans = 0;
        for (int d = 1; d <= n; ++d) {
            if (mu[d] == 0) continue;
            ans += mu[d] * g(n, d);
        }
        cout << "Crystal " << ++tc << ": " << ans << '\n';
    }
    return 0;
}

關鍵點總結

• 莫比烏斯函數 μ 將「不共線」轉化為容斥求和。
• g(d) 計算利用對稱性：座標範圍 [-N,N]，步長 d 的點數為 2⌊N/d⌋+1。
• 線性篩 O(MAXN) 預處理，單次查詢 O(N)，極快。