数论基础

Hdd大约 5 分钟...

数论基础部分

质数

定义：在大于 $1$ 的整数中，如果包含 $1$ 和本身这两个约数，那么这个数就是质数 (素数)。

质因数（素因数，质因子）在数论当中是指能够整除给定正整数的质数。
除 $1$ 之外，两个没有其他共同质因数的的正整数称为互质。
$1$ 与任何数互质。
正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。eg: $12=2×2×3=2^2×3$

【质数数量】在整个自然数集合中，质数的数量较少，分布稀疏，对于一个足够大的整数 $N$ ，不超过 $N$ 的质数大约有 $\frac{N}{lnN}$ 个，即每 $lnN$ 个数中大约有 $1$ 个质数。

试除法判断质数

若一个正整数 $N$ 为合数，则存在一个能整除 $N$ 的数 $T$ ，其中 $2≤T≤sqrt(n)$ 。

即:

判定是否为质数的方法。让 $n$ 去模 $2$ 到 $n$ 的每一个数，设枚举变量为 $i$ ，当 n % i == 0 成立时，则说明 $n$ 不是质数。又因为有：当 $i$ 可以整除 $n$ 时， $\frac{n}{i}$ 也可以整除 $n$ ，所以枚举的边界就变为: $i ≤ \frac {n} {i}$ ，即 $i^2 ≤ n$ 。

时间复杂度 $o(sqrt(n))$

// 判断是否为质数
pub fn is_prime(n: usize) -> bool {
  if n <= 2 { return false; }
  let sqrt_n = (n as f32).sqrt() as usize;
  for i in 2..sqrt_n {
    if n % i == 0 {
    	return false;
    }
  }
  true
}

bool is_prime(int n){
  if(n < 2) return false;
  for( int i = 2; i < n ; i++)
    if(n % i == 0)   // n 可以被 2~n 的整数整除
      return false;
  return true;
}

算术基本定理

任何一个大于 $1$ 的自然数 $N$ ，如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积。

N = p_1^{a_1}×p_2^{a_2}×p_3^{a_3}×...×p_n^{a_n}

这里 $p_i$ 均为质数，其中指数 $a_i$ 是正整数，且有 $p_1<p_2<p_3...<p_n$

试除法分解质因数

对于 $2$ ~ $⌊sqrt(n)⌋$ 的每个数 $i$ ，若 $i$ 能够整除 $n$ (即 n % i == 0)，则从 $n$ 中除掉所有的因子 $i$ (i为底数) ，同时累计除去的 $i$ 的个数 (个数为指数)。

一个合数的合数因子一定在扫描到这个合数 $n$ 之前就从 $n$ 中被除掉了. 根据算术基本定理，那些较小的合数因子一定会被合数因子小的质数表示掉. 又因为我们枚举的 i 是从小到大递增的，所以当 n % i == 0 时， i 一定为质数 .

例子

对 $12$ 进行质数分解：

12 / 2  =  6
6  / 2  =  3
3  / 2  =  1 (非整除，舍去)
3  / 3  =  1

12 从 2 开始被整除，12/2 = 6，然后看 6 能不能再被 2 整除，6/2=3 ，然后看 3 能不能被 2 整除，若不能，i + 1，然后循环往复.可以看到：12 的合数因子有 4， 6，但是在 i 递增到 4 的时候，12 已经被表示为 2×2×3 了。

时间复杂度 $o(sqrt(n))$

pub fn prime_factors(mut n: usize) -> Vec<(usize, usize)> {
  let mut v: Vec<(usize, usize)> = vec![];
  let sqrt_n = (n as f32).sqrt() as usize;
  for i in 2..sqrt_n + 1 {
    let mut cnt: usize = 0;
    if n % i == 0 {
      while n % i == 0 {
        n /= i;
        cnt += 1;
      }
      v.push((i, cnt));
    }
  }
  if n > 1 {
    v.push((n, 1));
  }
  v
}

试除法求约数

若 $d$ 是 $N$ 的约数（ $d≥sqrt(N)$ ），则 $N/d$ 也是 $N$ 的约数（ $N/d≤N$ ）。

即：

约数总是成对出现的（除了完全平方数， $sqrt(N)$ 会单独出现）。因此，只需扫描 $d = 1$ ~ $sqrt(N)$ ，尝试 $d$ 能否整除 $N$ ，若能整除，则 $N/d$ 也是 $N$ 的约数，

试除法的推论: 一个整数 $N$ 的约数上界为 $2sqrt(N)$

时间复杂度： $O(sqrt(N))$ 。

pub fn get_divisors(n: usize) -> Vec<usize> {
  let mut v: Vec<usize> = vec![];
  let sqrt_n = (n as f32).sqrt() as usize;
  for i in 1..sqrt_n + 1 {
    if n % i == 0 {
      v.push(i);
      if i != n / i {
        v.push(n / i);
      }
    }
  }
  v.sort();
  v
}

算术基本定理的推论

在算术基本定理中，若整数 $N$ 被唯一分解为 $N=p_1^{c_1}×p_2^{c_2}...p_m^{c_m}$ ，其中 $c_i$ 都是正整数， $p_i$ 都是质数，且满足 $p_1<p_2<...<p_m$ ，则 $N$ 的正约数集合可写作： $\{p_1^{b_1}×p_2^{b_2}×...×p_m^{b_m}\}$ ，其中 $0≤b_i≤c_i$

正约数个数

$N$ 个正约数个数为:

\prod\limits_{i=1}^{m}(c_i+1)=(c_1+1)×(c_2+1)×...×(c_m+1)

证明： $b_1 ... b_m$ 不同取法就对应着不同的约数。取法的个数就是约数的个数。 $b_1$ 有 $0$ ~ $c_1$ 这些选择，共有 $c_1 + 1$ 中选法。由乘法原理就可以得出约数的个数。

pub fn divisors_num(mut n: usize) -> u128 {
  let mut mp: HashMap<usize, usize> = HashMap::new();
  let sqrt_n = (n as f32).sqrt() as usize;
  for i in 2..sqrt_n + 1 {
    if n % i == 0 {
      let mut cnt = 0;
      while n % i == 0 {
        n /= i;
        cnt += 1;
      }
      mp.insert(i, cnt);
    }
  }
  if n > 1 {
    mp.insert(n, 1);
  }
  let mut res: u128 = 1;
  for (_, v) in mp {
    res = (res * (v + 1) as u128);
  }
  res
}

正约数之和

$N$ 的所有正约数的和为：

\prod\limits_{i=1}^{m} \Bigg(\sum_{j=0}^{c_i}(p_i)^j\Bigg) =(1+p_1+p_1^2+...p_1^{c_1})×...×(1+p_m+p_m^2+...+p_m^{c_m})

证明: 在算术基本定理的推论中，每个质因子的指数为 $b_i$ ，一个数的约数不止是质数，还有合数，而这些合数在算术基本定理中会被分解为 质数和质数的指数 。可以对正约数之和的式子展开，展开后为一定为： () + () + ... + () 的形式。则每个 () 就是约数.

秦九韶算法

$f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0=(...((a_nx + a_{n-1})x+a_{n-2})x+...+a_1)x+a_0$

pub fn divisors_sum(mut n: usize) -> usize {
  let mut mp: HashMap<usize, usize> = HashMap::new();
  let sqrt_n = (n as f32).sqrt() as usize;
  for i in 2..sqrt_n + 1 {
    if n % i == 0 {
      let mut cnt = 0;
      while n % i == 0 {
        n /= i;
        cnt += 1;
      }
      mp.insert(i, cnt);
    }
  }
  if n > 1 {
    mp.insert(n, 1);
  }

  let mut res: usize = 1;
  for (k, mut v) in mp {
    let mut t: usize = 1;

    // 秦九韶算法
    while v != 0 {
      t = t * k + 1;
      v -= 1;
    }
    res = res * t;
  }
  res
}