数学专题

首先是逆元,由于费马小定理,有     假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1,即为 a(p-1)≡1(mod p),两边同除以a,即有 a(p-2)≡ 1/a(mod p),也就是说,除以一个数a,在模的意义下是等于乘a(p-2)的。

首先是基础的,  这是组合数的公式

那么问题来了,C(m,n)%p怎么办?当这个值非常非常大的时候;

这时候,有一个玩意,叫lucas定理

Lucas定理:我们令n=sp+q , m=tp+r .(q ,r ≤p)
那么:

(在编程时你只要继续对

 

调用Lucas定理即可。

代码可以递归的去完成这个过程,其中递归终点为t = 0 ;
时间O(logp(n)*p):)
//注意,这份代码中是C(n,m),和上面数论中的C(m,n)中m、n有相反。
//这是求单次的,适用于少量的调用函数

LL exp_mod(LL a, LL b, LL p) {
    LL res = 1;
    while(b != 0) {
        if(b&1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}

LL Comb(LL a, LL b, LL p) {
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b; ++i) {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}

LL Lucas(int n, int m, int p) {
     LL ans = 1;

     while(n&&m&&ans) {
        ans = (ans*Comb(n%p, m%p, p)) % p;
        n /= p;
        m /= p;
     }
     return ans;
}


//这份适用于需要大量的调用函数
  mi[i]表示i的阶乘,inv[i]表示(i的阶乘)的p-2次方
  第一行求出了每个i的p-2次方,第二行求出阶乘。
inv[1]=1;for (i=2;i<mod;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
inv[0]=1;for (i=1;i<mod;i++)(inv[i]*=inv[i-1])%=mod;
	
ll c(int n,int m)
{
	if (n<m)return 0;
	if (n<mod)return mi[n]*inv[m]%mod*inv[n-m]%mod;
		else return c(n/mod,m/mod)*c(n%mod,m%mod)%mod;
}

对于上分代码中,为递推求逆元,递推式为inv[i]=(M-M/i)*inv[M%i]%M

差不多了,对于上述所有数论相关证明,详情请百度。