数论()-其他

发表于： 3月 19, 2023 3月 19, 2023
分类：其他
标签：其他

数论()

1.CRT中国剩余定理

2.拓展欧几里德

int exgcd(int a,int b,int &x,int &y){
	if(b==0){x=1;y=0;return a;}
	int d=exgcd(b,a%b,y,x);//d是最大公约数
	y-=a/b*x;return d;
}

对于\(ax+by=1\) ，
有解时\(1\%gcd(a,b)=0\) ，
得到\(bx_2+(a-a/b\times b)y_2=1\) ，
此时\(x=y_2,y=x_2-a/b\times y2\) ，
用辗转相除法得到最终\(b=0\)时，此时\(a\)即为\(gcd(a,b)\)，解为\(x=1,y=0\)。
解出最小解\(x_0\)。

此时\(y=(1-ax)/b\)，如果\(x\)要增加，那么保持\(y\)为整数，则\(x\)应加上\(b\)的倍数（因为\(gcd(a,b)=1\)，所以乘上\(a\)并无用）
然后得到\(x_i=x_0+kb\)，
要得到最小正整数解\(x_i\)，只要\(x_i=(x_0\%b+b)\%b\)。(如果b小于0:)

b=-b

一般题目里是\(ax+by=C\)，（\(C\)是\(gcd(a,b)\)的倍数的话，有解）
解出\(ax+by=1\)后，可以得到 \(axC+bxC=C\)，\(axC/(gcd(a,b))+bxC/(gcd(a,b))=C/(gcd(a,b)\)，
所以\(x\)乘上\(C/(gcd(a,b))\)。解出一组\(x\)后，其他解为\(x_i=x_0+kb/(gcd(a,b)\)。

证明：
\(ax_0+bx_0=C\)，\(ax_i+bx_i=C\)。
\(a/gcd(a,b)(x_i-x_0)=-b/gcd(a,b)(y_i-y_0)\)，
因为\(gcd(a,b)=1\)，
所以\((x_i-x_0)\%(b/gcd(a,b))=0)\)
所以\(x_i=x_0+kb/(gcd(a,b)\)。（PS：不太懂2022.10.11）

3.质因数分解

普通的质因数分解是\(O(\sqrt n)\)的。

int tmp=x;
for(int i=2;i*i<=x;i++){
	if(tmp%i)continue;
	cout<<tmp<<" ";
	while(tmp%i==0)tmp/=i;
}
if(tmp>1)cout<<tmp<<" ";

当然你可以打质数筛优化这个过程\(O(faster)\)。

for(int j=1;prime[j]<=sqrt(a[i]);j++){
	while(tmp%prime[j]==0){
		ans+=check(prime[j]);
		tmp/=prime[j];
	}
}
if(tmp>1)ans+=check(tmp);

4.线性求乘法逆元

首先，p为质数。

inv[1]=1;
inv[i]=(p-p/i)*(inv[p%i])%p;

5.lucas定理

\(C_{n}^{m}=C_{n/p}^{m/p}\times C_{n\%p}^{m\%p}\)
p为质数。

6.欧拉函数

套路是找到一个\(gcd(a,b)=c\)，变为\(gcd(a/c,b/c)=1\)。

phi[1]=1;bk[1]=1;
for(int i=2;i<=maxn;i++){
	if(!bk[i]){
		prime[++tot]=i;
		phi[i]=i-1;
	}
	for(int j=1;j<=tot;j++){
		if(i*prime[j]>maxn)break;
		bk[i*prime[j]]=1;
		phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
		if(i%prime[j]==0)break;
	}
}

你也可以质因数分解做（也可以用质数筛优化）

int phi(int x){
	int ans=x;int tmp=x;
	for(int i=2;i*i<=x;i++){
		if(tmp%i)continue;
		ans=ans/i*(i-1);
		while(tmp%i==0)tmp/=i;
	}
	if(tmp>1)ans=ans/tmp*(tmp-1);
	return ans;
}

7.组合数公式

\(C(n,k)=C(n,n-k)\)
\(C(n,k)+C(n,k+1)=C(n+1,k+1)\)
\(C(n,k+1)=C(n,k)\times (n-k)/(k+1)\)

8.欧拉筛

for(int i=2;i<=n;i++){
	if(bk[i]==0)prime[++tot]=i;
	for(int j=1;j<=tot;j++){
		if(prime[j]*i>n)break;
		bk[prime[j]*i]=1;
		if(i%prime[j]==0)break;
	}
}

9.高斯消元

10. 费马小定理

若\(x\)是\(a\mod p\)下的逆元，则\(x=a^{p-2}\)(\(p\)为质数) 。

11.拓欧求逆元

若\(x\)是\(a\mod p\)下的逆元，则\(x\times a=1(\mod p)\)，所以\(ax+py=1\)，那么用拓欧即可求出\(x\)

12.除法分块

\(\color{darkblue}\text{P2261 [CQOI2007]余数求和}\)

2147483647.其他

立方差公式：\(a^3-b^3=(a-b)(a^2+ab+b^2)\) 。
\(\sum_{i=1}^ni^2=n\times (n+1)\times (2n+1)/6\)。

————————