Codeforces 471C MUH and House of Cards (數學規律 + 枚舉)

問題描述

給定 n 張卡牌，搭建金字塔式結構：第 i 層需 2*i + (i-1) = 3i - 1 張牌。若搭建 k 層，總需 ∑(3i-1) = (3k+1)k/2 張。求有多少種層數 k 使得 (n + k) % 3 == 0 且總需求 ≤ n。

數學推導

• 第 i 層用牌：2i + (i-1) = 3i - 1。
• k 層總和：S(k) = (3k+1)k/2。
• 條件：S(k) ≤ n 且 (n + k) % 3 == 0（因每層模 3 餘 2，k 層總和模 3 餘 2k，需 n ≡ 2k (mod 3) → n+k ≡ 0 (mod 3)）。

算法

枚舉 k 從 1 到 sqrt(2n/3)，檢查上述條件，計數符合者。n ≤ 10⁹，k 最大約 2.6×10⁴，枚舉極快。

代碼 (C++)

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

int main() {
    ll n;
    while (cin >> n) {
        int ans = 0;
        for (ll k = 1; (3*k+1)*k/2 <= n; ++k) {
            if ((n + k) % 3 == 0) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

優化版 (無需預算上限)

觀察到每層減 2 為 3 的倍數，可直接枚舉層數 j，檢查 (n - 3*(j-1) - 2*j) % 3 == 0，但枚舉 k 已足夠高效。