一名提高选手的数论之路（二）-白红宇

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

阅读量：6511 次

发布时间：2019-06-24

本文共 2469 字，大约阅读时间需要 8 分钟。

1.乘法逆元（inv）两种求法：

First:（满足p为质数且a与p互质才可以使用）

根据费马小定理：

ap≡a(modp)

可得

ap−2≡a−1(modp)

由此可知，

ap−2modp即是a在模p意义下的逆元

然而

ap−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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long longusing 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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long longusing 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;}