【板子】gcd、exgcd、乘法逆元、快速幂、快速乘、筛素数、快速求逆元、组合数

清疚 2022-06-16 08:28 211阅读 0赞

转载至：[http][][://www.cnblogs.com/flipped/p/5716603.html][http]

#### 1.gcd ####

int gcd(int a,int b){ return b?gcd(b,a%b):a; }

#### 2.扩展gcd )extend great common divisor ####

![复制代码][copycode.gif]

ll exgcd(ll l,ll r,ll &x,ll &y) { if(r==0){
        x=1;y=0;return l;} else { ll d=exgcd(r,l%r,y,x); y-=l/r*x; return d; } }

![复制代码][copycode.gif]

#### 3.求a关于m的乘法逆元 ####

![复制代码][copycode.gif]

ll mod_inverse(ll a,ll m){ ll x,y; if(exgcd(a,m,x,y)==1)//ax+my=1
            return (x%m+m)%m; return -1;//不存在
    }

![复制代码][copycode.gif]

补充：求逆元还可以用

ans=abmodm=(amod(m⋅b))/b ans=abmodm=(amod(m⋅b))/b

#### 4.快速幂quick power ####

![复制代码][copycode.gif]

ll qpow(ll a,ll b,ll m){ ll ans=1; ll k=a; while(b){ if(b&1)ans=ans*k%m; k=k*k%m; b>>=1; } return ans; }

![复制代码][copycode.gif]

#### 5.快速乘,直接乘会爆ll时需要它，也叫二分乘法。 ####

![复制代码][copycode.gif]

ll qmul(ll a,ll b,ll m){ ll ans=0; ll k=a; ll f=1;//f是用来存负号的
        if(k<0){
        f=-1;k=-k;} if(b<0){
        f*=-1;b=-b;} while(b){ if(b&1) ans=(ans+k)%m; k=(k+k)%m; b>>=1; } return ans*f; }

![复制代码][copycode.gif]

#### 6.中国剩余定理CRT (x=ai mod mi) ####

![复制代码][copycode.gif]

ll china(ll n, ll *a,ll *m) { ll M=1,y,x=0,d; for(ll i = 1; i <= n; i++) M *= m[i]; for(ll i = 1; i <= n; i++) { ll w = M /m[i]; exgcd(m[i], w, d, y);//m[i]*d+w*y=1
            x = (x + y*w*a[i]) % M; } return (x+M)%M; }

![复制代码][copycode.gif]

#### 7.筛素数，全局：int cnt,prime\[N\],p\[N\]; ####

![复制代码][copycode.gif]

void isprime() { cnt = 0; memset(prime,true,sizeof(prime)); for(int i=2; i<N; i++) { if(prime[i]) { p[cnt++] = i; for(int j=i+i; j<N; j+=i) prime[j] = false; } } }

![复制代码][copycode.gif]

#### 8.快速计算逆元 ####

补充：>>[关于快速算逆元的递推式的证明][Link 1]<<

![复制代码][copycode.gif]

void inverse(){ inv[1] = 1; for(int i=2;i<N;i++) { if(i >= M) break; inv[i] = (M-M/i)*inv[M%i]%M; } }

![复制代码][copycode.gif]

#### 9.组合数取模 ####

n和m 10^5时，预处理出逆元和阶乘

![复制代码][copycode.gif]

ll fac[N]={
        1,1},inv[N]={
        1,1},f[N]={
        1,1}; ll C(ll a,ll b){ if(b>a)return 0; return fac[a]*inv[b]%M*inv[a-b]%M; } void init(){
        //快速计算阶乘的逆元
        for(int i=2;i<N;i++){ fac[i]=fac[i-1]*i%M; f[i]=(M-M/i)*f[M%i]%M; inv[i]=inv[i-1]*f[i]%M; } }

![复制代码][copycode.gif]

n较大10^9，但是m较小10^5时，

![复制代码][copycode.gif]

ll C(ll n,ll m){ if(m>n)return 0; ll ans=1; for(int i=1;i<=m;i++) ans=ans*(n-i+1)%M*qpow(i,M-2,M)%M; return ans; }

![复制代码][copycode.gif]

n和m特别大10^18时但是p较小10^5时用lucas

#### 10.Lucas大组合取模　 ####

![复制代码][copycode.gif]

#define N 100005
    #define M 100007 ll n,m,fac[N]={
        1}; ll C(ll n,ll m){ if(m>n)return 0; return fac[n]*qpow(fac[m],M-2,M)%M*qpow(fac[n-m],M-2,M)%M;//费马小定理求逆元
    } ll lucas(ll n,ll m){ if(!m)return 1; return(C(n%M,m%M)*lucas(n/M,m/M))%M; } void init(){ for(int i=1;i<=M;i++) fac[i]=fac[i-1]*i%M; }

![复制代码][copycode.gif]

### ###

[http]: http://www.cnblogs.com/flipped/p/5716603.html
[copycode.gif]: /images/20220616/3c247ac6242d4d2c9347b80e07b4d60e.png
[Link 1]: http://www.cnblogs.com/flipped/p/5701879.html