URAL 1083 Factorials!!!：多階乘計算詳解

URAL 1083 是一道極其基礎但考察閱讀理解與邊界處理的題目。給定整數 n (1 ≤ n ≤ 10) 和 k 個感嘆號 (1 ≤ k ≤ 20)，要求計算多階乘 n!!!…!（共 k 個 !）。

一、數學定義精讀

題目給出兩種等價定義：

1. 若 k 不整除 n：n!!!…! = n × (n−k) × (n−2k) × … × (n mod k)
2. 若 k 整除 n：n!!!…! = n × (n−k) × (n−2k) × … × k

本質上就是：從 n 開始，每次減 k，直到項 ≤ 0 為止，但最後一項必須 > 0。等價於 ∏(n - i*k) for i=0..t where n-i*k > 0。

二、樣例驗證

Input: 9 !! （n=9, k=2）
計算: 9 × 7 × 5 × 3 × 1 = 945
Output: 945 ✓

三、算法實現

由於 n ≤ 10，結果極小（最大 10! = 3,628,800），int 或 long long 完全足夠，無需大整數。直接模擬即可。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string s;
    // 注意：輸入可能包含多行測試用例，直到 EOF
    while (cin >> n) {
        if (!(cin >> s)) break; // 讀取感嘆號字符串
        int k = s.size();        // k = 感嘆號個數
        
        long long ans = 1;
        for (int x = n; x > 0; x -= k) {
            ans *= x;
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵點解析：

• 循環條件：x > 0 完美涵蓋兩種定義。當 k 整除 n 時，最後一項為 k (>0)；不整除時，最後一項為 n mod k (>0)。
• 輸入處理：感嘆號作為字符串讀取，長度即為 k，避免字符逐個讀取的麻煩。
• 多測試用例：題目未給定用例數，採用 while (cin >> n >> s) 讀至 EOF。

四、複雜度分析

• 時間：O(n/k) ≤ O(10)，瞬間完成。
• 空間：O(1)。

五、常見錯誤與避坑指南

1. 誤以為需要大整數：n ≤ 10，最大值 10! = 3,628,800，32 位有符號整數（21 億）綽綽有餘。
2. 循環終止條件寫錯：寫成 x >= k 或 x > k 會漏乘最後一項（如 9!! 會漏乘 1）。
3. 忽略多行輸入：必須循環讀取直到 EOF。
4. 感嘆號包含空格：題目說「n 後恰好一個空格，然後 k 個感嘆號」，用 string s; cin >> s; 可自動跳過空格讀取連續非空白字符。

六、延伸思考

若 n 範圍擴大（如 ≤ 1000），結果將超出 64 位整數，需引入大整數乘法（如 Python 內建 int、C++ boost::multiprecision::cpp_int 或手寫高精度）。但本題約束極小，純屬熱身題，重在準確理解定義並正確實現邊界。