数论

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]\)

性质

积性函数

逆元