数论杂

1、O(cnt*log)（==O(n)）阶乘质因数分解：
求n阶乘：先筛出质数，再对n跑每个质数。

F(j,1,cnt){
		x=n*2;
		while(x){
			a[j]+=x/prm[j];x/=prm[j];
		}	
	}

2、
线性逆元：
inv[0]=inv[1]=1;
F(i,2,n){inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;};
3、
线性阶乘逆元：
注：处理mod较大情况。（1e9+7,998244353)
对于小mod,可被整除的，直接算都会变成零。处理方法：见下。
jc[0]=jc[1]=1;
    
    F(i,2,n){
        jc[i]=jc[i-1]*i%mod;
    }
    inv[end]=qpow(jc[end],mod-2);
    for(int i=end-1;~i;--i){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
小mod处理方法：const int end=min(n,mod-1)
只计算mod一下的阶乘逆元。mod以上阶乘逆元都是零。
qpow算出mod-1，从mod-2开始找。
否则算出来都是零。