ライブラリ/整数(C++) - 個人用メモ

##hightlight(linenumber,cpp){{
long long gcd(long long a,long long b){

return b>0?gcd(b,a%b):a;

}

long long lcm(long long a,long long b){

return a/gcd(a,b)*b;

}

long long extgcd(long long a,long long b,long long &x,long long &y){

long long d=a;
if(b!=0){
	d=extgcd(b,a%b,y,x);y-=(a/b)*x;
}else{
	x=1;y=0;
}
return d;

}

long long mod_inverse(long long a,long long M){

long long x,y;
extgcd(a,m,x,y);
return (m+x%m)%m;

}

long long mod_pow(long long a,long long n,long long M){

if(n==0)return 1%M;
long long res=mod_pow(a*a%M,n/2,M);
if(n&1)res=res*a%M;
return res;

}

vector<int> divisor(int n){

vector<int> res;
for(int i=1;i*i<=n;i++){
	if(n%i==0){
		res.push_back(i);
		if(i*i!=n)res.push_back(n/i);
	}
}
return res;

}

bool miller_rabin(long long n){

if(n==2)return true;if((n&1)==0||n<=1) return false;
int a[]={2,3,5,7,11,13,17,-1},r;long long s=0,d,x;
d=n-1;
while((d&1)==0)s++,d=d>>1;
for(int i=0;a[i]!=-1&&a[i]<n;i++){
	if((x=mod_pow(a[i],d,n))!=1){
		for(r=0;r<s;r++){
			if(x==n-1)break;
			x=(x*x)%n;
		}
		if(r==s)return false;
	}
}
return true;

}