lucas的代码实现

发布网友发布时间：2024-04-06 07:58

共1个回答

热心网友时间：2024-04-22 11:40

c++
求C(n, m) mod 10007 int Lucas (ll n , ll m , int p) { return m == 0 ? 1 : 1ll*comb (n%p , m%p , p) * Lucas (n/p , m/p , p) % p ;}//comb()函数中，因为q ， r < p , 所以这部分暴力完成即可。 C++ 求C(n, m) mod 10007 版本二要求p z在100000左右ll f[N];void init(int p) { //f[n] = n! f[0] = 1; for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;} ll pow_mod(ll a, ll x, int p) { ll ret = 1; while (x) { if (x & 1) ret = ret * a % p; a = a * a % p; x >>= 1; } return ret;} ll Lucas(ll n, ll k, int p) { //C (n, k) % p ll ret = 1; while (n && k) { ll nn = n % p, kk = k % p; if (nn < kk) return 0; //inv (f[kk]) = f[kk] ^ (p - 2) % p ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p; n /= p, k /= p; } return ret;} int main(void) { init (p); printf (%I64d\n, Lucas (n, m, p)); return 0;}见右图，参考冯志刚《初等数论》第37页。