数论合集

数论

Date:2023.1.14

素数（质数）

定义

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

$1$ 既不是素数也不是合数

判断素数

朴素算法

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

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

埃式筛法

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

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

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

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

时间复杂度：$O(nInInn)$（$Inn$表示$lo{g}_{e}n$）

#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");
}

欧拉筛法（线性筛法）

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

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

时间复杂度：$O(n)$

#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");
}

注意，以上两个筛法都是求$1-n$中的素数

分解质因数

这还不简单

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

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

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

最后若$n>0$，也要算一个素数

时间复杂度：$O(logn)$

#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 _{i=1}^k{p}_i^{a_i}=p_1^{a_1}\ast p_2^{a_2}\ast \cdots \ast p_k^{a_k}$

则 1 的约数个数为：

$f(n)=\prod _{i=1}^k(a_i+1)=(a_1+1)\ast (a_2+1)\ast \cdots \ast (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)\ast (a_2+1)\ast \cdots \ast (a_k+1)$

时间复杂度：$O(\sqrt{n})$

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

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

时间复杂度：$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,amodb)$

证明：

设 $a=bk+c$，则 $c=amodb$

设 $d|a,a|b$，则 $c=a-bk,\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k$

反过来，

设 $d|b,d|(amodb)$

则 $\frac{amodb}{d}=\frac{a}{d}-\frac{b}{d}k$

移项得：$\frac{amodb}{d}+\frac{b}{d}k=\frac{a}{d}$

显然，$\frac{amodb}{d}\in Z$

$\therefore \frac{a}{d}\in Z$，即 $d|a$

得证

时间复杂度：$O(logn)$

#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\ast b=gcd(a,b)\ast 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\ast b=gcd(a,b)\ast lcm(a,b)$

时间复杂度：$O(logn)$

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

欧拉函数

定义

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

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

性质

积性函数

逆元