整除
前置
整除定义: 如果 \(\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)\) 。
线性筛的部分过程图。
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\) 的数都可以被有限质数相乘的形式。
其中 \(p_1<p_2<...p_n\) 均为质数,\(c_i\) 均为正整数。
正约数个数为:
正约数之和为:
分级质因数
试除法:与判质数的试除法相似,只要一个数是 \(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)\) 是偶数。
欧拉函数的通项公式:
证明:若 \(n=p^{k}\) ,则 \(\varphi(n)=p^{k}-p^{k-1}\) 。
由唯一分解定理可知:
又因为欧拉函数是积性函数
求解欧拉函数
求单个数的欧拉函数时,枚举质因数按照公式求就可以了,时间复杂度: \(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);
}
}
一个点 \((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;
}