mg4377娱乐娱城官网_mg4377娱乐手机版_www.mg4377.com

bzoj2982 -- 卢卡s定理

时间:2019-08-02 19:12来源:mg4377娱乐手机版
Lucas定理裸题。。 题目 bzoj2982 -- 卢卡s定理。Lucas定理供给mod为素数 [图表上传失败...(image-139989-1517648456435)] 大家仍可以对 Lucas定理:C(n,m)=C(n%p,m%p)*C(n/p,m/p)%p #includestdio.h#include string.husing

Lucas定理裸题。。

题目
bzoj2982 -- 卢卡s定理。Lucas定理供给mod为素数

[图表上传失败...(image-139989-1517648456435)]
大家仍可以对

Lucas定理:C(n,m)=C(n%p,m%p)*C(n/p,m/p)%p

#include<stdio.h>
#include <string.h>
using namespace std;
#define Mod 1000000007
typedef long long LL;
LL mod;
/*
根据费马小定理:

已知(a, p) = 1,则 a^(p-1) ≡ 1 (mod p),  所以 a*a^(p-2) ≡ 1 (mod p)。

也就是 (m!)的取模逆元为 (m!)^p-2 ;
*/
LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= mod;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
LL C(LL a, LL b) {
    if(a < b)   return 0;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b;   i) {
        ca = (ca * (a - i))%mod;
        cb = (cb * (b - i))%mod;
    }
    ans = (ca*quick_mod(cb, mod - 2)) % mod;
    return ans;
}
LL Lucas(LL n,LL m)
{
    if(m==0) return 1;
    return C(n%mod,m%mod)*Lucas(n/mod,m/mod);
}
int main()
{
    int t;
    scanf("%d",&t);
    LL a,b;
     while(t--)
        {
            scanf("%I64d%I64d%I64d",&a,&b,&mod);
        printf("%I64dn",Lucas(a,b));
        }
}

图片 1

预处理出阶乘、逆元的阶乘就能够了。

继续调用Lucas定理。

编辑:mg4377娱乐手机版 本文来源:bzoj2982 -- 卢卡s定理

关键词: 日记本 数论