数论模板

const int N=1e6+10;
vector<int> prime;
bool isprime[N];
int sum[N];
void Getprime(int n){
	for(int i=2;i<=n;i++){
		if(!isprime[i]){
			prime.push_back(i);
			sum[i]=sum[i-1]+1;
		}
		else sum[i]=sum[i-1];
		for(int j=0;prime[j]<=n/i;j++){
			isprime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int gcd(int a,int b){
	while(b){
		int t=b;
		b=a%b;
		a=t;
	}
	return a;
}

int qpow(int n,int m,int p){
	if(m==0) return 1%p;
	if(m%2) return n*qpow(n,m-1,p)%p;
	int temp=qpow(n,m/2,p)%p;
	return temp*temp%p;
}

int qpow(int n,int m,int p){
	int ans=1%p;
	while(m){
		if(m&1) ans=ans*n%p;
		n=n*n%p;
		m>>=1;
	}
	return ans;
}