欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

我的数论模板

程序员文章站 2024-03-19 10:03:46
...

我的数论模板

最大公因数

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

扩展欧几里得

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

线性筛

bool isprime[100000005];
int prime[10000000];
const long long maxn=1e8; 
//1e5------ 9593
//1e6------ 78499
//1e7------ 664580
//1e8------ 5761456
void Prime()
{
	memset(isprime,1,sizeof(isprime));
	mu[1]=1;a[1]=1;
	int temp=0;
	for(int i=2;i<maxn;i++)
	{
		if(isprime[i]) prime[++temp]=i;
		for(int j=1;j<=temp&&prime[j]*i<maxn;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	 } 
 } 
 void Mu()
{
	memset(isprime,1,sizeof(isprime));
	mu[1]=1;a[1]=1;
	int temp=0;
	for(int i=2;i<maxn;i++)
	{
		if(isprime[i]) prime[++temp]=i,mu[i]=-1;
		for(int j=1;j<=temp&&prime[j]*i<maxn;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
		a[i]=a[i-1]+mu[i];
	 } 
 } 

快速幂

int qpow(int a,int b,long long mod)
{
	long long ans=1;
	long long base=a;//数据小的时候可以用int 
	while(b)
	{
		if(b&1) ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}

质数分解

int factor[100000000][2];
int getFactor(int x)
{
	int cnt=0;
	for(int i=1;prime[i]*prime[i]<=x;i++)
	{
		if(x%prime[i]==0)
		{
			factor[cnt][0]=prime[i];
			int temp=0;
			while(x%prime[i]==0)
			{
				x/=prime[i];
				temp++;
			}
			factor[cnt++][1]=temp;
		}
	}
	if(x!=0)
	{
		factor[cnt][0]=x;
		factor[cnt++][1]=1;
	}
	return cnt;
 } 

乘法逆元

 //费马小定理版 
 int inv(int x,long long mod)
 {
 	return qpow(x,mod-2);
 }
 //扩展欧几里得版
 int inv(int x)
 {
 	int x,y;
 	if(exgcd(x,mod,x,y)!=1)
 	{
	 	return -1;
 	}
 	return ((x%mod)+mod)%mod//保证返回的是正数 
  } 

中国剩余定理

复习的话可以看这里

//x%a=m
long long China(int n,long long a[],long long m[])
{
	long long M=1,ret=0;
	for(int i=0;i<n;i++) M*=m[i];
	for(int i=0;i<n;i++)
	{
		long long  w=M/m[i];
//		cout<<"+++++++++++++++"<<endl;
		ret=(ret+w*inv(w,m[i])*a[i])%M;
//		cout<<"---------3246"<<endl;
	}
	return (ret + M)%M;
}