基础数论(第一版)

· · 算法·理论

注:本文中的所有字母或未知数均为整数,有特殊条件的会单独声明。

Part 1.常见数学符号

  1. 整除符号:x|y 表示 x 整除 yxy 的因数。
  2. 取模符号:x \bmod y 表示 x 除以 y 得到的余数。
  3. 互质符号:x \perp y 表示 xy 互质。
  4. 最大公约数:\gcd(x,y) 表示 xy 的最大公约数。
  5. 最小公倍数:\operatorname{lcm}(x,y) 表示 xy 的最小公倍数。
  6. 求和符号:\sum 表示满足特定条件的数的和。
  7. 阶乘符号:n! 表示 1 \times 2 \times 3 \times \dots \times n 的计算结果。
  8. 求积符号:\prod 与求和符号作用相似,只是把和改成了积。

    Part 2.质数

    如果这个数大于一且只有一和他本身两个因数的数叫做质数,反之为合数。
    特别的,01 既不是质数也不是合数。

    关于质数的筛法

    方法一:暴力求解,用于判断一个数是不是质数,所用时间相对较多,面对多个数据或大数据时不建议使用。

bool pd(int x){
    if(x==1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}

方法二:用埃氏筛,从 2 开始,将每个素数的各个倍数,标记成合数。一个素数的各个倍数,是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处,后者是以素数来测试每个待测数能否被整除,时间复杂度为 O(n \log n)

void eartos(int n){
    int i,j;
    prime[0]=prime[1]=false;
    for(i=2;i<=n;i++)
        prime[i]=true;
    for(i=2;i<=n;i++){
        if(prime[i]){
            for(j=i*i;j<=n;j+=i){
                prime[j]=false;
            }
        }
    }
}

方法三:用线性筛(欧拉筛),对所有的数先扫一遍,当扫到第 i 个数时如果这个数先前未被标记则保存到素数表中,然后筛掉当前的素数表中的每一个数与这个数的乘机和这个数的平方,如果已被标记则直接跳过并筛掉部分它的倍数,具体筛掉那些见下面的代码(注:此代码源自 oi-wiki)。
由于所有合数只被标记了一遍,所以时间复杂度为 O(n)

vector<int> pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之,i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的,所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉,就不需要在这里先筛一次,所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

方法二和方法三的两种筛法用于求所有的(或多个)质数。

Part 3.同余

当整数 a 和整数 b 除以整数 m 的余数为同一个数是 a \equiv b \pmod m ,或者说,若 m 是正整数,ab是整数,且 m|(a-b)(a-b)\%m=0,则称 abm 同余。
把同余当作一种运算,是因为同余满足运算的诸多性质:

  1. 它满足自反性(一个数永远和自己同余)。
  2. 对称性(ab 同余,ba 也就同余)。
  3. 传递性(ab 同余,bc 同余可以推出 ac 同余)。

一些定理和性质

Part 4.快速幂

对于快速计算 a^b \bmod c 这个式子大家应该都学过二分快速幂,但是我们也都知道位运算是一个非常快的运算符,所以理论上可以用位运算来求这个式子(注:abc 均为正数)。
但有的时候它太快了,甚至超出了 long long 的数据范围,需要慢一点。
以上这两种快速幂的方法个人不太建议使用,多数时候都建议写二分快速幂。
位运算快速幂代码如下:

int quick_pow(int a,int b,int mod){
    int ans=0;
    while(b){
        if(b&1)ans=(ans+a)%mod;
        b=b>>1;
        a=(a<<1)%mod;
    }
    return ans;
}

慢的快速幂代码如下:

int mul(int a,int b,int mod){
    int ans=0;
    while(b){
        if(b&1) ans=(ans+a)%mod;
        b>>=1;
        a=(a<<1)%mod;
    }
    return ans;
}
int fst(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=mul(ans,a,p);
        a=mul(a,a,p);
        b>>=1;
    }
    return ans;
} 

Part 5.拓展欧几里得算法

在看这个部分之前请先看上面的同余
已知现在有一个方程 ax+by=c 让你求解(abc 均为常数)。
解这个方程之前先看这个方程 ax+by=\gcd(a,b),解除此方程的解 x0y0,那么前面那个方程的解就是 x=x0 \times \frac{c}{\gcd(a,b)}y=y0 \times \frac{c}{\gcd(a,b)},但这是个二元一次方程,并且还是 a+b=c 的形式,所以这个方程要么无解,要么有无限解。

既然有有无限解了,那怎么求它的通解?

最小正整数解

## Part 6.欧拉函数 欧拉函数通常用符号 $\varphi$ 来表示,如果 $n$ 为一个正整数,那么 $\varphi(n)$ 就表示从 $1$ 到 $n$ 的所有与 $n$ 互质的整数的个数,欧拉函数是积性函数。 ### 欧拉函数的通式 求欧拉函数有两个通式,分别是 $\varphi(n)=n \times (1-\frac{1}{p_1}) \times \dots \times (1-\frac{1}{p_n})$ 和 $\varphi(n)=p^k-p^{k-1}=p-1 \times p^{k-1}$。 通式一中的 $p_1,p_2,\dots,p_n$ 分别为 $n$ 的所有质因数,通式二需满足整数 $n$ 是质数 $p$ 的 $k$ 次幂。 ### 欧拉函数的性质 性质一:若 $a$ 与 $b$ 互质,那么 $\varphi(a \times b)=\varphi(a) \times \varphi(b)$。 性质二:若 $p$ 是质数,那么 $\varphi(p)=p-1$。如果 $i \bmod p=0$ 那么 $\varphi(i \times p)=\varphi(i) \times p$,否则 $\varphi(i \times p)=\varphi(i) \times (p-1)$。 ### 求一个数的欧拉函数 可以直接质因数分解,直接统计次数。 ```cpp int euler(int x){ int i,a=x,ans=x; for(i=2;i*i<=a;i++){ if(a%i==0){ ans=ans-ans/i; while(a%i==0)a=a/i; } } if(a>1)ans=ans-ans/a; return ans; } ``` ### 求多个数的欧拉函数 利用埃氏筛,每次发现质因子时把它的倍数的欧拉函数乘上 $\frac{p-1}{p}$ 这样就可以一次性求出 $1$ 到 $n$ 的所有数的欧拉函数的值。 ```cpp void eartos_euler(int x){ int i,j; for(i=1;i<=x;i++)phi[i]=i; for(i=2;i<=n;i++){ if(phi[i]==i){ for(j=i;j<=n;j+=i) phi[j]=phi[j]/i*(i-1); } } } ``` ## Part 7.费马小定理的基础性质 若 $p$ 为质数,且 $a$ 和 $p$ 互质,则可以得到 $a^{p-1} \equiv 1 \pmod p$,和 $a^b \bmod p=a^{b \bmod (p-1)}(\bmod p)$。 一般情况下,在 $p$ 是一个质数的情况下,对任意整数 $a$ 都有 $a^p \equiv a \pmod p$。 ## Part 8.欧拉定理 在整数 $p$ 不是质数的情况下,$a^{\varphi(p)} \equiv 1 \pmod p$。 当 $m$ 是质数时代入上面的公式可得 $a^{m-1} \equiv 1 \pmod m$。因此,欧拉定理也可以看做时费马小定理的加强版。 **欧拉定理的降幂**:已知$a$ 与 $b$ 互质,当 $b$ 很大时,可用欧拉定理降幂,$a^b \bmod n=a^{b \bmod \varphi(n)} \bmod n$。 **拓展(广义)欧拉定理**:$a^b \bmod c=a^{b \bmod \varphi(c)+\varphi(c)}\bmod c$。 ## Part 9.逆元 当 $a$ 与 $b$ 互质时若 $a \times x \equiv 1 \pmod m$ 则称 $x$ 是 $a$ 关于模 $m$ 的逆元,逆元是正数,也是唯一的。 **欧拉定理求逆元**:若 $m$ 是质数,那么 $a^{m-2} \equiv a^{-1} \pmod m$,然后就可以直接快速幂求解了,时间复杂度为 $O(n \log n)$。 ```cpp ll ksm(ll x,ll t){ ll res=1; while(t){ if(t&1)res=res*x%mod; x=x*x%mod;t>>=1; } return res%mod; } ``` **拓展欧几里得算法求逆元**:已知方程 $(a \times x)\bmod b=1$ 等价于 $a \times x=1+y \times b$ 也等价于 $a \times x + y \times b =1$。 如果 $a$ 与 $b$ 互质,则方程等价于 $a \times x-b \times y=\gcd(a,b)$。 因此求解 $x$ 的过程就是求解该二元一次方程组,并且在该方程组之中 $a$ 与 $b$ 已知,求解 $x$,即求 $a$ 模 $b$ 的逆元。 当 $a$ 与 $b$ 互质时,$a$ 的逆元存在,$x$ 为最小正整数解且只需要负转正得该逆元为 $(x \bmod b + b)\bmod b$。若 $a$ 与 $b$ 不是互质的关系,那么此逆元不存在,时间复杂度与前文中的拓展欧几里得算法差不多。 ```cpp int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return a; } else{ int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } } signed main(){ cin>>n>>b; c=exgcd(a,b,x,y); if(c==1)ans=(x%b+b)%b; else ans=-1; cout<<ans; return 0; } ``` **线性求逆元**:设 $inv_i$ 表示 $i$ 的逆元,$p$ 为给出的需要模的数,则可以得到递推式:$inv_i=(p-\frac{i}{p})\times inv_{p \bmod i} \bmod p$。当求到第 $inv_i$ 项时,$inv_{p \bmod i}$ 已经算好了,时间复杂度为 $O(n)$。 ```cpp inv[0]=inv[1]=0; for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p; ``` ## 完结撒花!