数论整理

目录

• 求最小公倍数
  • 辗转相除法
• 求素数
  • 埃式筛
  • 欧拉筛
• 求解逆元（mod N）
  • 扩展欧几里德

求最小公倍数

辗转相除法

gcd(a,b)=>gcd(b,a%b)

ll gcd(ll a,ll b)
{
	if(!b)return a;
	else return gcd(b,a%b);
}

求素数

埃式筛

//复杂度O(nloglogn)
for(long long i=2;i<=n;i++)
	{
		if(prime[i])
		{
			for(long long j=i*i;j<=n;j=j+i)//i*i更加高效
			{
				prime[j]=false;
			}
		}
	}

欧拉筛

for(int i=2;i<n;i++)
	{
		if(is_prime[i])
			prime.push_back(i);
		for(int j=0;j<prime.size()&&i*prime[j]<maxn;j++)
		{
			is_prime[i*prime[j]]=false;
			if(i%prime[j]==0)break;
			//i//prime[j]=m,则i*prime[j+1]=m*prime[j]*prime[j+1]=prime[j]*n,且n>i,prime[j]<prime[j+1],因此i*prime[j+1]一定会在未来当i=n时被筛去
			//保证了每个合数仅被它最小的质因子筛除一次，提高效率
		}
	}

求解逆元（mod N）

扩展欧几里德

void extend_euclid(ll a,ll b,ll &d,ll &x,ll &y)
{
	if(!b)
	{
		d=a;x=1;y=0;
		return;
	}
	else
	{
		extend_euclid(b,a%b,d,y,x);
		y=y-(a/b)*x;
	}
}
cout<<(x+p)%p;