数论

Date:2023.1.14

素数（质数）

定义

只有两个因数的数叫做质因数（1和它本身）

1 既不是素数也不是合数

判断素数

朴素算法

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

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

埃式筛法

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

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

我们知道，对于一个 x ∈ Z，它的倍数一定是约数

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

时间复杂度：$\color{orange}O(n\, In\, In\,n)$（In n表示logen）

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）$

这里给出证明：

由约数的定义可得：p1a1有p10, p11, p12…p1a1这些约数，共有(a1 + 1)个

同理，p2a2有(a2 + 1)个约数，…pkak有(ak + 1)个约数

∴ p1a1中有(a1 + 1)个因子，…pkak中有(ak + 1)个因子

乘法原理可得：fn = (a1 + 1) * (a2 + 1) * … * (ak + 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 = p1ka1p2ka2…pskas, b = p1kb1p2kb2…pskbs

则 gcd(a, b) = p1min(ka1, kb1)p2min(ka2, kb2)…psmin(kas, kbs)

lcm(a, b) = p1max(ka1, kb1)p2max(ka2, kb2)…psmax(kas, kbs)

∵ka + kb = min(ka, kb) + max(ka, kb)

∴ 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;
}

欧拉函数

定义

欧拉函数，即 φ(n)，表示小于等于 n 且与 n 互质数的个数

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

性质

积性函数

逆元