数论

Date:2023.1.14

素数(质数)

定义

只有两个因数的数叫做质因数(1和它本身)

\(1\) 既不是素数也不是合数

判断素数

朴素算法

枚举 \(2-(n-1)\)的所有数字,判断其是否能被整除,时间复杂度:\(\color{orange}O(n)\)

或者可以优化一下,枚举区间改成 \(2-\sqrt{n}\),时间复杂度:\(\color{orange}O(\sqrt{n})\)

埃式筛法

对于多个大数,朴素算法显然慢了

对于求多个质数,我们可以运用标记思想

我们知道,对于一个 \(x\in Z\),它的倍数一定是约数

所以我们可以从小到大的枚举 \(n\) 内的质数,标记它的倍数,没被标的即是质数

时间复杂度:\(\color{orange}O(n\, In\, In\,n)\)\(In\, n\)表示\(log_en\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<cmath>
#define N 10005
using namespace std;
int n;
int f[N],ss[N],cnt;
void ssai(int x){
for(register int i=2;i<=x;i++){
if(!f[i]) ss[++cnt]=i;
for(register int j=2;j<=n;j++){
if(ss[cnt]*j>n) break;
f[ss[cnt]*j]=1;
}
}
}
int main(){
scanf("%d",&n);
ssai(n);
for(int i=1;i<=cnt;i++) printf("%d\n",ss[i]);
system("pause");
}

欧拉筛法(线性筛法)

我们回忆一下埃式筛法,对于一个约数,它可能被多个素数标记,浪费了时间

那么欧拉筛法就只让一个约数被他最小的质因子标记

时间复杂度:\(\color{orange}O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<cmath>
#define N 10005
using namespace std;
int n;
int f[N],ss[N],cnt;
void ssou(int x){
for(register int i=2;i<=n;i++){
if(!f[i]) ss[++cnt]=i;
for(register int j=1;j<=cnt;j++){
if(ss[j]*i>n) break;
f[i*ss[j]]=1;
if(i%ss[j]==0) break;
}
}
}
int main(){
scanf("%d",&n);
ssou(n);
for(int i=1;i<=cnt;i++) printf("%d\n",ss[i]);
system("pause");
}

注意,以上两个筛法都是求\(\color{red}1-n\)中的素数

分解质因数

这还不简单

算数基本定理(唯一分解定理):任何一个约数都可以被分解成几个素数相乘的形式

根据这条定理,我们可以采用试除法

\(2-\sqrt{n}\) 枚举 \(n\) 的质数 ,遇到素数就一直除以它,直到不能整除为止,并记录除的次数

最后若\(\color{red}n>0\),也要算一个素数

时间复杂度:\(\color{orange}O(logn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<math.h>
using namespace std;
int n;
int dpf(int x){
int sum=0;
for(int i=2;i<=sqrt(x);i++)
while(x%i==0){
x/=i;
sum++;
}
if(x>1) sum++;
return sum;
}
int main(){
scanf("%d",&n);
int ans=dpf(n);
printf("%d",ans);
return 0;
}

合数

合数,通俗理解:不是素数的正整数就是合数(1 除外)

定义

除了 1 和它本身之外还有其他因数的数叫合数

1 既不是素数也不是合数

判断合数

应该没有这种题吧

先用欧拉筛法,加个标记,没被标的即使合数

这么简单,不用放代码吧

求约数个数

约约数个数定理:对于一个大于 1 的正整数可以 分解质因数

\(n=\prod\limits_{i=1}^{k}p_i^{a_i}=p_1^{a_1}*p_2^{a_2}*\dots *p_k^{a_k}\)

则 1 的约数个数为:

\(f(n)=\prod\limits_{i=1}^{k}(a_i+1)=(a_1+1)*(a_2+1)*\dots*(a_k+1)\)

这里给出证明:

由约数的定义可得:\(p_1^{a_1}\)\(p_1^0,p_1^1,p_1^2\dots p_1^{a_1}\)这些约数,共有\((a_1+1)\)

同理,\(p_2^{a_2}\)\((a_2+1)\)个约数,\(\dots p_k^{a_k}\)\((a_k+1)\)个约数

\(\therefore p_1^{a_1}\)中有\((a_1+1)\)个因子,\(\dots p_k^{a_k}\)中有\((a_k+1)\)个因子

乘法原理可得:\(f_n=(a_1+1)*(a_2+1)*\dots*(a_k+1)\)

时间复杂度:\(\color{orange}O(\sqrt{n})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<math.h>
using namespace std;
int n;
int dpf(int x){
int cnt=0,sum=1;
for(int i=2;i<=sqrt(x);i++){
while(x%i==0){
x/=i;
cnt++;
}
sum*=(cnt+1);
}
if(x>1) sum*=2;
return sum;
}
int main(){
scanf("%d",&n);
int ans=dpf(n);
printf("%d",ans);
return 0;
}

如果你要求所有约数,用质因数一个个乘吧

时间复杂度:\(\color{orange}O(n)\)

公约数&公倍数

公约数

定义

若 x 同时是 a 和 b 的约数,则称 x 是 a 与 b 的公约数

公倍数

定义

若 a 和 b 同时是 x 的约数,则称 x 是 a 与 b 的公倍数

最大公约数

定义

若 x 是 a 和 b 的公约数且 x 最大,则称 x 是 a 和 b 的最大公约数

\(gcd(a,b)=x\)

求最大公约数

\(gcd(a,b)=gcd(b,a\,mod\,b)\)

证明:

\(a=bk+c\),则 \(c=a\, mod\, b\)

\(d\,|\,a,a\,|\,b\),则 \(c=a-bk,\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k\)

反过来,

\(d\,|\,b,d\,|\,(a\,mod\,b)\)

\(\frac{a\,mod\,b}{d}=\frac{a}{d}-\frac{b}{d}k\)

移项得:\(\frac{a\,mod\,b}{d}+\frac{b}{d}k=\frac{a}{d}\)

显然,\(\frac{a\,mod\,b}{d}\in Z\)

\(\therefore \frac{a}{d}\in Z\),即 \(d\,|\,a\)

得证

时间复杂度:\(\color{orange}O(logn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<math.h>
using namespace std;
int a,b;
int gcd(int x,int y){
if(!b) return a;
return gcd(b,a%b);
}
int main(){
scanf("%d%d",&a,&b);
int ans=gcd(a,b);
printf("%d",ans);
return 0;
}

补充

\(\gcd(a,b)=1\),我们称这两个数 互质

即最大的公约数为 1

最小公倍数

定义

若 x 是 a 和 b 的公倍数且 x 最小,则称 x 是 a 和 b 的最小公倍数

\(lcm(a,b)=x\)

求最小公倍数

\(a*b=\gcd(a,b)*lcm(a,b)\)

证明:

\(a=p_1^{k_{a_1}}p_2^{k_{a_2}}\dots p_s^{k_{a_s}},b=p_1^{k_{b_1}}p_2^{k_{b_2}}\dots p_s^{k_{b_s}}\)

\(gcd(a,b)=p_1^{min(k_{a_1},k_{b_1})}p_2^{min(k_{a_2},k_{b_2})}\dots p_s^{min(k_{a_s},k_{b_s})}\)

\(lcm(a,b)=p_1^{max(k_{a_1},k_{b_1})}p_2^{max(k_{a_2},k_{b_2})}\dots p_s^{max(k_{a_s},k_{b_s})}\)

\(\because k_a+k_b=min(k_a,k_b)+max(k_a,k_b)\)

\(\therefore a*b=gcd(a,b)*lcm(a,b)\)

时间复杂度:\(\color{orange}O(logn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<math.h>
using namespace std;
int a,b;
int gcd(int x,int y){
if(!b) return a;
return gcd(b,a%b);
}
int main(){
scanf("%d%d",&a,&b);
int ans=gcd(a,b);
printf("%d",a*b/ans);
return 0;
}

欧拉函数

定义

欧拉函数,即 \(\varphi(n)\),表示小于等于 n 且与 n 互质数的个数

\(\varphi(n)=\sum\limits_{i=1}^n[gcd(i,n)=1]\)

性质

积性函数

逆元