CPC23-4-K 喵喵的神數：Lucas 定理與組合數取模

CPC23-4-K 喵喵的神數：數論題目解析

給定 T 和質數 P，求 ∑_{i=1}^{T} C(T, i) mod P 的值。題目利用 Lucas 定理將大數組合數取模轉化為小數組合數乘積。

核心數學推導

由 Lucas 定理：C(n, m) mod p = C(n%p, m%p) * C(n/p, m/p) mod p。題目中 m = p，代入得：

C(T, p) mod p = C(T%p, 0) * C(T/p, 1) mod p
             = 1 * (T/p) mod p
             = (T/p) % p

因此答案簡化為 (T / P) % P，無需複雜組合數計算。

極簡 AC 代碼

#include 
using namespace std;
int main() {
    int n, t, p;
    cin >> n;
    while (n--) {
        cin >> t >> p;
        cout << (t / p) % p << endl;
    }
    return 0;
}

題目陷阱與心得

關鍵在於識別 m = p 這一特殊條件，直接套用 Lucas 定理化簡。若嘗試通用組合數模板會超時或實現複雜。數論題目常需敏銳發現數學性質，而非單純編程技巧。