数论

质数

一些结论

质数分布 $\pi (x)$为不大于x的质数的个数，有 $\pi (x)\approx \frac{x}{\ln_{}{x} }$

质数近似估计 第x个质数的近似估计：$x\ln_{}{x}$

欧拉筛

时间复杂度为 $O(n \log n \log n)$

线性筛

cpp
1
2
3
4
5
6
7
8
9
void pre(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
			vis[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
} 

分解质因数

法一

如果被分解的数不太大，可以使用线性筛筛出小于等于它的所有质数。枚举每个质数，再一个一个试除

法二

事实上，即使被分解的数到了 $10^{12}$ 的范围，也是可以用上述方法的

考虑到原数只可能有一个大于 $\sqrt{n}$ 的质因子，所以我们只需要筛出 $\sqrt{n}$ 以内的质数，然后再一个个试除

除到最后如果不为1的话，那么剩下那个数就是原数最后的质因子

法三

在线性筛时，vis数组不单纯记录有没有被筛掉，而是记录被哪个数字筛掉了。最后根据vis数组就可以做到分解质因数

cpp
1
2
3
4
5
6
7
8
9
10
int prime[_],cnt,vis[_];
inline void init(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[++cnt]=i,vis[i]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
			vis[prime[j]*i]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
}

cpp
1
2
3
4
5
6
7
8
9
while(t--){
	int x;cin>>x;
	int ans=0;
	while(x!=1){
		ans^=vis[x];
		x/=vis[x];
	}
	cout<<ans<<endl;
}

约数

一些结论

将正整数N分解为 $N=p_1^{c_1}p_2^{c_2}p_3^{c_3}...p_m^{c_m}$
则有：

N的正约数的个数为 $\prod_{i=1}^{m} (c_i+1)$

N的所有正约数之和为 $\prod_{i=1}^{m} (\sum_{j=0}^{c_i}(p_i)^j )$

$lcm(ma,mb)=m\times lcm(a,b)$

$a\times b=gcd(a,b)\times lcm(a,b)$

欧几里得算法 $gcd(a,b)=gcd(b,a \bmod b)$

更相减损术 $gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)$ $(a\ge b)$

高精度求gcd

若a和b均为偶数，$gcd(a,b)=2\times gcd(a/2,b/2)$；

若a为偶数b为奇数，$gcd(a,b)=gcd(a/2,b)$；

若a和b均为奇数，$gcd(a,b)=gcd(a-b,b)$

同余

一些结论

费马小定理

若 $a,p$ 互质且 $p$ 为质数，则有 $a^{p-1}\equiv 1\pmod{p}$
进一步推得 $a^b \equiv a^{bmod(p-1)}\pmod{p}$

扩展欧拉定理

对于任意 $a,m$ 都有

exgcd

cpp
1
2
3
4
5
6
int exgcd(int a,int b,int &x,int &y){
	if(!b){return x=1,y=0,a;
	int r=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return r;
}

$exgcd(a,b,x,y)$ 即可求出方程 $ax+by=gcd(x,y)$ 一组特解 $x,y$

求出解的增量： $dx=b/gcd(a,b),dy=a/gcd(a,b)$

与原方程的倍数： $d=c/gcd(a,b)$

得原方程的特解： $x\ast =d,y\ast =d$

然后可以利用增量来调整解

比如，若 $x<0$ 则可以 $x\bmod dx+dx$ 来调整到x的最小非负整数解

excrt

cpp
1
2
3
4
5
6
7
8
9
10
11
12
int excrt(){
	int M=m[1],A=a[1],x,y,d;
	for(int i=1;i<=n;i++){
		d=exgcd(M,m[i],x,y);
		if((A-a[i])%d!=0) return -1;
		x=((A-a[i])/d*x%(m[i]/d)+m[i]/d)%(m[i]/d);//可能这一步需要龟速乘
		A-=x*M;
		M=M/d*m[i];
		A=(A%M+M)%M;
	}
	return A;
}

逆元

exgcd求逆元

cpp
1
2
3
int b,p,x,y;
exgcd(b,p,x,y);
x=(x%p+p)%p;

x即为b在模p下的逆元

时间复杂度 $O(log n)$

费马小定理求逆元

要求p必须为质数

cpp
1
int x=qpow(b,p-2,p);

x即为b在模p下的逆元

时间复杂度 $O(log n)$

线性推连续逆元

cpp
1
2
3
4
5
int n,p;
inv[0]=0,inv[1]=1;
for(int i=2;i<=n;i++){
  inv[i]=p-(p/i)*inv[p%i]%p;
}

时间复杂度 $O(n)$

线性推阶乘逆元

常用于组合数取模

cpp
1
2
3
4
5
6
7
8
9
10
11
const int mod; 
int fac[1000006];
int inv[1000006];
void pre(){
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=pow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
} 

时间复杂度 $O(n)$

线性推数列逆元

借助线性推乘法逆元的思想

对于数列 $a_1,a_2,a_3...,a_n$

定义 f[i]=f[i-1]*a_i%mod;

先求最后一项的逆元 g[n]=qpow(f[n],mod-2);

然后线性推 g[i]=g[i+1]*a[i+1]%mod;

则对于 $a_i$ 的逆元，为 g[i]*f[i-1]%mod

其他

矩阵快速幂

1. 生成单位矩阵的时候只需要一层循环

2. Matrix结构体的arr数组记得要memset

3. 看好数据范围，可能需要龟速乘

欧拉函数

一些结论

$n= {\textstyle \sum_{d|n}^{}}\varphi (d)$

除了2以外，其他数的欧拉函数值都为偶数

$\varphi(p^k)=p^k-p^{k-1}$

如果 $gcd(a,x)=1$ 那么 $gcd(x-a,a)$。因此，与x互质的数是成对出现的，并且和为x。由此可知，小于n与n互质的所数的和为 $\varphi(n)\times n/2$

暴力推欧拉函数

cpp
1
2
3
4
5
6
7
8
9
inline int euler(int x){
	int phi=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0) phi=phi/i*(i-1);///
		while(x%i==0) x/=i;
	}
	if(x>1) phi=phi/x*(x-1);
	return phi;
}

线性筛欧拉函数

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int phi[_],vis[_],prime[_],cnt;
void pre(){
	phi[1]=1;///
	for(int i=2;i<=_-6;i++){
		if(!vis[i]) prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prime[j]<=_-6;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];///
				break;
			}else{
				phi[i*prime[j]]=phi[i]*phi[prime[j]];///
			} 
		}
	}
}

数论分块

用于求 $\sum_{i=1}^{n}\frac{x}{i}$

我们发现一些 $\frac{x}{i}$ 的值是相同的，将相同的作为一个块

设 $t=\frac{x}{i}$ 为当前块的特征值（也就是当前块所有的数都等于这个）

如果 $t=0$ ，那么当前块的右边界为n

如果 $t\neq 0$ ，那么当前块的右边界为 $\frac{n}{t}$