每日算法——卢卡斯定理

关键词

卢卡斯定理

题目描述

给定三个整数 n, m, p, 求 C_n^{m} \mod p。

输入描述

1 \leq m \leq n \leq 10^9, 2 \leq p \leq 10^5, 保证 p 为质数。

输出描述

输出1行，为一个整数，表示答案。

示例

输入

5 2 3

输出

1

知识点

卢卡斯定理：

对于质数 p, 有C^n_m \mod p = C^{\lfloor n/p \rfloor}_{\lfloor m/p \rfloor} \cdot C^{n \mod p}_{m\mod p} \mod p

解决方案

阶乘

long long fact(int n) {
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        ans *= i;
    }
    return ans;
}

求组合数

long long C(int n, int m) {
    return fact(m) / (fact(n) * fact(m-n));
}

卢卡斯定理

long long Lucas(int n, int m, int p) {
    if (m == 0) return 1;
    return (C(n % p, m % p) * Lucas(n / p, m / p, p)) % p;
}