一名提高选手的数论之路（二）

本文主要是介绍一名提高选手的数论之路（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.乘法逆元（inv）两种求法：
First:（满足p为质数且a与p互质才可以使用）
根据费马小定理： $a^p\equiv a\pmod p$
可得 $a^{p-2}\equiv a^{-1}\pmod p$
由此可知， $a^{p-2}\mod p$ 即是a在模p意义下的逆元
然而 $a^{p-2}$ 可以轻易用快速幂算出
Second:（无条件）
通过扩展欧几里得算法来求： $exgcd(a,p,x,y)$
如此调用，x便是求得的a在模p意义下的逆元
不要问我为什么，我不想（zhi）说（dao）
记得答案是这样的(x+p)%p，因为要防止求出负数
代码就不用了吧。

2.在 $O(n)$ 内求前n个逆元：
这是偶然从一个人的博客里看见的。
首先inv[1]=1
然后inv[i]=(M-M/i)*inv[M%i]%M
如此从2一直递推到n就可以了。
具体证明可以看出处
代码很简单：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int n,M;
int inv[100001];
int main(){scanf("%d %d",&n,&M);inv[1]=1;for(int i=2;i<=n;i++){inv[i]=(M-M/i)*inv[M%i]%M;}for(int i=1;i<=n;i++){printf("%d ",inv[i]);}return 0;
}

3.Lucas定理：（注意，在算阶乘数组的时候，必须从a[0]开始初始化，不然有可能错。）
这个定理是用来求大组合数取模的结果的。
具体证明呀什么的可以自己百度。
我这里给个公式：
C(n,m)=C(n%p,m%p)*C(n/p,m/p)
然后在计算的时候，只要递归地去计算右半部分就可以了，左半部分可以预处理出阶乘直接算，记得边算边取模就好。

//这是洛谷的模板题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
ll ksm(ll a,ll b,ll p){a%=p;ll ans=1;while(b){if(b&1){ans=(ans*a)%p;}a=a*a%p;b>>=1;}return ans;
}
ll a[100001];
ll cm(ll n,ll m,ll p){if(m>n)return 0;return (a[n]*(ksm(a[m],p-2,p))%p*(ksm(a[n-m],p-2,p))%p);
}
ll lucas(ll n,ll m,ll p){if(m==0)return 1;return (cm(n%p,m%p,p)%p*lucas(n/p,m/p,p)%p);
}
int main(){int T;scanf("%d",&T);for(int o=1;o<=T;o++){ll n,m,p;scanf("%lld%lld%lld",&n,&m,&p);memset(a,0,sizeof(a));a[0]=1;for(int i=1;i<=100000;i++){a[i]=(a[i-1]*i)%p;}printf("%lld\n",lucas(n+m,n,p));}return 0;
}

4.中国剩余定理（CRT）：
用来求线性同余方程组，常用作合并答案
具体自己百度，我也没很弄懂，只是背了公式。

//代码未经测试，极有可能出错，仅供参考
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll q=exgcd(b,a%b,y,x);y-=a/b*x;return q;
}
ll inv(ll a,ll p){ll x,y;exgcd(a,p,x,y);return (x+p)%p;
} 
ll CRT(int n,ll *a,ll *m){ll M=1;for(int i=1;i<=n;i++){M*=m[i];}ll ans=0;for(int i=1;i<=n;i++){ll t=M/m[i];ll x=inv(t,m[i]);ans=(ans+a[i]*t*x)%M;}return (ans+M)%M;
}
int n;
ll a[100001];
ll m[100001];
int main(){return 0;
}