整除

2024-02-15 21:46 由 hutongzhou 发表于 #其他

前置
素数
- 素数的判定
- 素数筛法
约数
欧拉函数
- 欧拉函数的通项公式：
- 求解欧拉函数

前置

整除定义： 如果 $\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$
的方式。

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

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

快速线性筛法的原理是利用每个数 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;
}

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

前置

素数

素数的判定

素数筛法

约数

唯一分解定理

分级质因数

求约数集合

最大公约数与最小公倍数

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

欧拉函数

欧拉函数的通项公式：

求解欧拉函数