BZOJ 2257 瓶子與燃料 - 數學歸納與約數枚舉

問題描述

有若干固定容量的瓶子。火星人每次操作：從一瓶倒到另一瓶、倒掉一瓶、裝滿一瓶。每次給你能給出的最少燃料。你想從 k 個瓶子中獲得燃料，求最多能獲得多少。

核心洞察

可獲得的燃料量必為所有瓶子容量的公約數。因為操作本質是線性組合：任意時刻瓶中燃料量均為容量的整數線性組合（貝祖定理）。最小正線性組合即為 gcd。因此，k 個瓶子能給出的最少燃料 = 這 k 個瓶子容量的 gcd。

問題轉化為：從所有瓶子中選 k 個，使其 gcd 最大。等價於：找出一個數 d，使得至少 k 個瓶子容量是 d 的倍數，且 d 最大。

算法：枚舉約數

1. 收集所有瓶子容量的所有約數（至多 1000 萬級，實際較少）。
2. 統計每個約數出現的次數（即有多少瓶子是其倍數）。
3. 從大到小遍歷約數，第一個出現次數 ≥ k 的即為答案。

代碼實現（C++）

#include 
using namespace std;
const int MAX = 10000010;
int cnt[MAX];

void addDivisors(int x) {
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            cnt[i]++;
            if (i != x / i) cnt[x / i]++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    for (int i = 0, x; i < n; i++) { cin >> x; addDivisors(x); }
    for (int d = MAX - 1; d >= 1; d--) {
        if (cnt[d] >= k) { cout << d << '\n'; break; }
    }
    return 0;
}

複雜度

枚舉約數 O(n√V)，V 為最大容量。統計數組大小 O(V)。優化：只枚舉出現過的約數並排序，空間更小。