2018-team4-modules-Lucas定理

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
int Lucas(LL x,LL y) {
    if (y > x) return 0;
    if (x <= p && y <= p) return C[x][y];
    return Lucas(x/p,y/p) * Lucas(x%p,y%p) % p;
}
}}}

//C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
int Lucas(LL x,LL y) {
    if (y > x) return 0;
    if (x <= p && y <= p) return C[x][y];
    return Lucas(x/p,y/p) * Lucas(x%p,y%p) % p;
}