整除

前置

整除定义: 如果 \(\frac{a}{b}∈Z\) , 称 \(b\) 整除 \(a\)\(a\)\(b\) 整除, 记为 \(b∣a\)

性质 1: \(n\) 的约数有 \(1\) ,\(n\) 第二大的约数最多有 \(n\) 的一半。

性质 2: \(a \mid b\) ,\(a \mid c\) 可知 \(a\mid kb\pm lc\) ,其中 \(k,l∈Z\)

素数

定义: 质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

定理 1: 在自然数集中,小于 \(n\) 的质数约有 \(\frac{n}{ln(n)}\) 个。

素数的判定

试除法,时间复杂度:\(O(\sqrt n)\)

实现方法:设 \(a∣n,a\le \frac{n}{a}\) ,那 \(\frac{n}{a}∣n\)\(a^{2}\le n,a \le \sqrt n\)

code

code
bool check(int x)
{
	if(x<2)return 0;
	for(int i=2;i<=sqrt(x);i++)
	if(x%i==0)return 0;
	return 1;
}

素数筛法

1.埃氏筛

算法原理:如果 \(x\) 是合数,那么 \(x\) 的倍数也是合数,这样可以筛掉所以的合数,剩下的就是质数。

我们可以优化一下上面的算法,从小到大枚举,把每一个质数的倍数都筛掉。

code
void prime(int n)
{
  	for(int i=2;i<=n;i++)
	{
		if(vis[i])continue;
		p[++m]=i;
		for(int j=1;j*i<=n;j++)
		vis[j*i]=1;
	}
}

时间复杂度:\(O(nloglogn)\) ,证明:外层循环 \(n\) 次,内层循环每一次都是 \(\frac{n}{i}\) ,所有就是 $n+\frac{n}{2}+\frac{n}{3}+ \cdots +\frac{n}{n} $ ,用调和级数 \(f(n)=1+\frac{1}{2}+\frac{1}{3}+ \cdots +\frac{1}{n}\) ,可知当 \(n\) 趋近无穷时,调和级数极限是 \(ln(n)+C\) 其中 \(C\) 是常数。而我们筛数的时候只用了质数,所以式子变成了 \(f(n)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{5}\cdots +\frac{1}{n}\) 。时间复杂度是 \(O(loglogn)\) ,总复杂度为 \(O(nloglogn)\)

2.欧拉筛

埃氏筛法即使在优化后任然会重复标记合数,即每个合数都可能被筛去多次。比如 \(24\) ,既会被 \(3\) 标记,也会被 \(4\) 标记,即:\(24=3*8\)\(24=4*6\)。其原因在于没有确定出唯一产生 \(24\)
的方式。

欧拉筛是埃氏筛的改进,我们保证每个合数只会被它的最小质因子筛掉。

根据算术基本定理(唯一分解定理),任何大于1的自然数,都可以唯一分解成有限个,质数的乘积的形式,且经过适当排序其写法唯一。(在下一节会较详细的讲解)。也就是说,任何大于1的自然数至少有一个素数因子。

快速线性筛法的原理是利用每个数 i 的最小素因子来筛素数,即筛去 \(i\)\(prime[1]\) 倍、\(prime[2]\) 倍、\(\cdots\)\(prime[j]\) 倍,要保证 \(prime[j]≤v[i]\) ,即标记到最小质因子的倍数就停止了。这就使每个合数只可能被筛去一次,提高了效率。

时间复杂度:\(O(n)\)

线性筛的部分过程图。

P3383 【模板】线性筛素数

code
#include<bits/stdc++.h>
using namespace std;
const int N=200000000+10;
int n,q,m;
int prime[N];
bool vis[N];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prime[++m]=i;
		for(int j=1;j<=m,prime[j]*i<=n;j++)
		{
			vis[prime[j]*i]=1;
			if(i%prime[j]==0)break;
		}
	}
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",prime[x]);
	}
	return 0;
 } 

欧拉筛在后面筛其他数时也有一定关联,这将会放在第四章筛法中讲解。

例题:

约数

唯一分解定理

定义:任何一个大于 \(1\) 的数都可以被有限质数相乘的形式。

\[N=\prod_{i=1} ^{m}p_i^{c_i} \]

其中 \(p_1<p_2<...p_n\) 均为质数,\(c_i\) 均为正整数。

正约数个数为:

\[N=\prod_{i=1}^{m}(c_i+1) \]

正约数之和为:

\[N=\prod_{i=1}^{m}(\sum_{j=0}^{c_i}(p_j)^{j}) \]

分级质因数

试除法:与判质数的试除法相似,只要一个数是 \(n\) 的因数,就一直除直到除不尽为止。

时间复杂度:\(O(\sqrt n)\)

code
void fj(int x)
{
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			fc[++cnt]=i;
			while(x%i==0)x/=i,num[i]++;
		}
	}
	if(x>1)fc[++cnt]=x,num[x]++;
	for(int i=1;i<=cnt;i++)
	cout<<fc[i]<<" "<<num[fc[i]]<<endl;
}

最小质因子法: 依托欧拉筛可以求出每个数的最小质因子,可以直接除以数的最小质因子来分解质因数。

code
void fj(int x)
{//s[]是最小质因子
	for(int i=2;i<=1000;i++)
	{
		if(!vis[i])prime[++m]=i,s[i]=i;
		for(int j=1;j<=m,prime[j]*i<=1000;j++)
		{
			vis[prime[j]*i]=1;
			s[prime[j]*i]=prime[j];
			if(i%prime[j]==0)break;
		}
	}
	while(x>1)
	{
		if(!num[s[x]])fc[++cnt]=s[x];
		num[s[x]]++;
		x/=s[x];
	}
	for(int i=1;i<=cnt;i++)
	cout<<fc[i]<<" "<<num[fc[i]]<<endl;
}

求约数集合

试除法:求单个数的约数集合。

与判质数的试除法相似,显然约数是成对出现,所以每次加入集合时要加两次。

时间复杂度:\(O(\sqrt n)\)

code
vector<int>res;
void factor(int n)
{
	for(int i=1;i*i<=n;i++)
	{
		if(n%i!=0)continue;
		res.push_back(i);
		if(n/i!=i)res.push_back(n/i);
	}
}

倍数法:\(1\)\(n\) 每一个数的正约数的集合。

与埃氏筛相似,枚举每一个数的两个约数。

时间复杂度近似于:\(O(nlogn)\)

code
vector<int>res[N];
void factor(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;i*j<=n;j++)
		res[j*i].push_back(j);
	}
}

例题:

最大公约数与最小公倍数

定义:
两个数 \(a\)\(b\) 的最大公约数(Greatest Common Divisor)是指同时整除 \(a\)\(b\) 的最大因数,记为 \(\gcd(a,b),(a,b)\)

两个数 \(a\)\(b\) 的最小公倍数 (Leatest Common Multiple) 是指同时被整除 \(a\)\(b\) 除的最小倍数,记为 \(lcm(a,b),[a,b]\)

性质1:\(\gcd(a,b)=\gcd(b,a)\)

性质2:\(\gcd(a,b,c)=\gcd(a,\gcd(b,c))\)

性质3:\(\gcd(a,b)=\gcd(b,a-b)\)

性质4:\(\gcd(a,b)=\gcd(b,a\% b)\)

性质5:\(\gcd(ka,kb)=k*\gcd(a,b)\)

性质6:\(\gcd(k,ab) \Leftrightarrow \gcd(k,a)=1,\gcd(k,b)=1\)

性质7:$ lcm(a,b)*\gcd(a,b)=ab$,特别的当 \(\gcd(a,b)=1\) 时,\(a\) ,\(b\) 互质,并且\(lcm(a,b)=ab\)

性质8:\(\gcd(F(a),F(b))=F(\gcd(a,b))\)

求解 \(\gcd(a,b)\)

1.辗转相除法(欧几里得法)

\(\forall a,b \in N,b \neq 0 , \gcd(a,b)=\gcd(b,a \% b)\) ,也就是性质4。

证明:\(a=kb+r=kb+a\% b,a%b=a-kb\),设 \(d\)\(a,b\) 的公因数,则 \(d \mid a,d \mid b\),由整除性质2得 \(d \mid (a-kb)\),即 \(d \mid (a \% b)\) ,所以性质成立。

时间复杂度:\(O(logn)\)

code
int \gcd(int a,int b)
{
	if(!b)	return a;
	return \gcd(b,a%b);
}

2.更相减损术

\(\gcd(a,b)=\gcd(a,a-b)\) ,也就是性质3。

证明:设 \(d=\gcd(a,a-b),a=k_1*d,a-b=k_2*b,\gcd(k1,k2)=1\),可以推出 \(b=(k_1-k_2)*d\)。所以\(\gcd(a,b)=\gcd(k_1*d,(k_1-k_2)*d)=d=\gcd(a,a-b)\)

这个方法时间复杂度有些低下,所以我们要进行优化。

根据性质5,可以想到如果两个数可以快速的找到两者的公因数,就可以一定的减少计算量,从而降低时间复杂度。最容易判断的是:是否都为 \(2\) 的倍数,于是就可以改写成 \(\gcd(2a,2b)=2*\gcd(a,b)\)

这个方法改进后还是不如上一个方法,在一般的求解时不会用它,但在需要求两个大数(要写高精)的最大公因数时,就比上一个方法好了。

P2152 [SDOI2009] SuperGCD(高精\gcd模板)

code
#include<bits/stdc++.h>
#define N 10009
using namespace std;
int x[9][N],l[9],cnt;
bool dayu(int a,int b){
	if(l[a]!=l[b])return l[a]>l[b];
	for(int i=l[a];~i;i--)
		if(x[a][i]!=x[b][i]) return x[a][i]>x[b][i];
	return 0;
}
int pl(int a,int b){
	l[a]=max(l[a],l[b]);
	x[a][l[a]]=0;
	for(int i=0;i<l[a];i++)x[a][i]+=x[b][i];
	for(int i=0;i<l[a];i++)
		x[a][i+1]+=x[a][i]/10,x[a][i]%=10;
	if(x[a][l[a]]) l[a]++;
	return a;
}
int mi(int a,int b){
	for(int i=0;i<l[a];i++){
		if(x[a][i]<x[b][i])
			x[a][i]+=10,x[a][i+1]--;
		x[a][i]-=x[b][i];
	}
	while(!x[a][l[a]-1])
		if(l[a]) l[a]--;
		else break;
	return a;
}
int mu2(int a){
	for(int i=0;i<l[a];i++)x[a][i]<<=1;
	for(int i=0;i<l[a];i++)
		x[a][i+1]+=x[a][i]/10,x[a][i]%=10;
	if(x[a][l[a]]) l[a]++;
	return a;
}
int de2(int a){
	for(int i=l[a]-1;i;i--)
		x[a][i-1]+=(x[a][i]&1)*10,
		x[a][i]>>=1;
	x[a][0]>>=1;
	if(!x[a][l[a]-1]) l[a]--;
	return a;
}
char as[N],bs[N];
int seize(int a,int b){
	if(!l[b]) return a;
	if((x[a][0]&1)==1&&(x[b][0]&1)==1){
		if(dayu(b,a)) swap(a,b);
		return seize(b,mi(a,b));
	}
	if((x[a][0]&1)==0&&(x[b][0]&1)==0)
		return mu2(seize(de2(a),de2(b)));
	if((x[a][0]&1)==0) a=de2(a);
	if((x[b][0]&1)==0) b=de2(b);
	return seize(a,b);
}
int main(){
	int a=++cnt,b=++cnt,c;
	scanf("%s%s",&as,&bs);
	l[a]=strlen(as);
	l[b]=strlen(bs);
	for(int i=0;i<l[a];i++) x[a][l[a]-1-i]=as[i]-'0';
	for(int i=0;i<l[b];i++) x[b][l[b]-1-i]=bs[i]-'0';
	c=seize(a,b);
	for(int i=l[c]-1;~i;i--)
		printf("%d",x[c][i]);
	return 0;
}

欧拉函数

定义:\(1 \cdots n\) 中与 \(n\) 互质的数量为欧拉函数,记为 \(\varphi(n)\)

性质1\(n\) 为质数时 \(\varphi(n)=n-1\)

性质2:\(p\) 为质数, \(p \mid n,p^{2} \mid n\) ,则 \(\varphi(n)=\varphi(\frac{n}{p}) \times p\)

性质3:\(p\) 为质数,$p \mid n,p $

性质4:\(n>2\) 时,\(\varphi(n)\) 是偶数。

欧拉函数的通项公式:

\[\varphi(N)=N \times \prod_{p \mid N} \frac{p-1}{p} \]

证明:若 \(n=p^{k}\) ,则 \(\varphi(n)=p^{k}-p^{k-1}\)
由唯一分解定理可知:

\[\varphi(n)=\varphi(\prod_{i=1}^{m}p_i^{k_i}) \]

又因为欧拉函数是积性函数

\[\begin{aligned} \varphi(n)&=\prod_{i=1}^{m} \varphi(p_i^{k_i})\\ &=\prod_{i=1}^{m}(p^{k}-p^{k-1})\\ &=\prod_{i=1}^{m}p_i^{k_i} \times \frac{p_i-1}{p_i}\\ &=n\times \prod_{i=1}^{m} \frac{p_i-1}{p_i}\\ &=n\times \prod_{p \mid n}\frac{p_i-1}{p_i}\\ \end{aligned} \]

求解欧拉函数

求单个数的欧拉函数时,枚举质因数按照公式求就可以了,时间复杂度: \(O(\sqrt n)\)

求解 \(1 \cdots n\) 的欧拉函数时,以欧拉筛为基础,套用性质1,性质2,性质3可线性筛出。

code
phi[1]=1;
for(int i=2;i<=n;i++)
{
	if(!vis[i])p[++m]=i,phi[i]=i-1;
	for(int j=1;j<=m,p[j]*i<=n;j++)
	{
		vis[i*p[j]]=1;
		if(i%p[j]==0)
		{
			phi[i*a[j]]=phi[i]*p[j];
			break;
		}
		else phi[i*p[j]]=phi[i]*(p[j]-1);
	}
}

例题:P2158 [SDOI2008] 仪仗队

一个点 \((x,y)\) 可以看到,当且仅当 \(\gcd(x,y)=1\),而欧拉函数就是和这个数互质的个数,所以我们只用求 \(3+2 \times \sum_{i=1}^{n}\varphi(n)\) 就可以了。

code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int f[N],a[N];
bool vis[N];
long long ans;
int main()
{
	scanf("%d",&n);
	if(n==1)
	{
		puts("0");
		return 0;
	}
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])a[++m]=i,f[i]=i-1;
		for(int j=1;j<=m,a[j]*i<=n;j++)
		{
			vis[i*a[j]]=1;
			if(i%a[j]==0)
			{
				f[i*a[j]]=f[i]*a[j];
				break;
			}
			else f[i*a[j]]=f[i]*(a[j]-1);
		}
	}
	for(int i=2;i<=n-1;i++)
	ans+=f[i];
	cout<<ans*2+3;
	return 0;
}

热门相关:最牛兵王   第一强者   绝代疯少   铁血大明   上古传人在都市