gcd，扩展gcd，乘法逆元，快速幂，快速乘，中国同余定理，

Myth丶恋晨 2021-12-08 22:39 276阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    //gcd
    LL gcd(LL a,LL b){
    	return b?gcd(b,a%b):a;
    }
    //扩展gcd：已知ax+by=gcd(a,b)，求x,y。 返回值是lr的gcd值。
    LL exgcd(LL a,LL b,LL &x,LL &y){
    	if(b==0){
    		x=1;
    		y=0;
    		return a;
    	}else{
    		LL d=exgcd(b,a%b,y,x);
    		y-=a/b*x;
    		return d;
    	}
    }
    //求a关于m的乘法逆元 
    LL mod_inverse(LL a,LL m){
    	LL x,y;
    	if(exgcd(a,m,x,y)==1)return (x%m+m)%m;//am的gcd==1
    	return -1;
    }
    //快速幂 
    LL qpow(LL a,LL b,LL m){//求欧拉函数，abm 
    	LL ans=0,k=a%m;
    	while(b){
    		if(b&1)ans=ans*k%m;//如果次方数是奇数
    		k=k*k%m;//底数平方下
    		b>>=1;  
    	}
    	return k; 
    }
    //快速乘，直接乘会爆的时候，使用快速乘，也叫作二分乘法
    LL qmul(LL a,LL b,LL m){
    	LL ans=0,f=1,k=a;
    	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 k; 
    } 
    //中国同余定理：CRT，https://www.cnblogs.com/DreamlessDreams/p/8710539.html见博客解释
    LL China(LL n,LL *a,LL *m){//要保证m互相之间互质， 
    	LL M=1,y,x=0,d;
    	for(int i=1;i<=n;i++)M*=m[i];//求积
    	for(LL i=1;i<=n;i++){
    		LL w=M/m[i];//ax+by=1;//  m[i]*d+w*y   
    		exgcd(m[i],w,d,y);//m[i]*d+w*y=1   w*y=1/m[i]
    		x=(x+y*w*a[i])%M;
    	}
        return (x+M)%M;
    	 
    }