质数

• 试除法，判定n是否是质数，时间复杂度 O(N*SQRT(N))

  // 就是一个2到sqrt(n)的遍历
  bool isPrime(int n) {
      if (n <= 1) return false;
      for (int i = 2; i <= n / i; i++) if (n % i == 0) return false;
      return true;
  }
  

• 线性筛法

  int primes[N], cnt;     // primes[]存储所有素数
  bool st[N];         // st[x]存储x是否被筛掉
  
  // 线性筛的原理是基于埃式筛，避免重复筛的情况，定义一个合数一定是被其最小质因子筛去的
  void getPrimes(int n) {
      for (int i = 2; i <= n; i++) {
          if (!st[i]) primes[cnt++] = i;
        	// （1）. 如果 i % primes[j] == 0， 那么 primes[j] 一定是 i 最小质因子
        	// （2）. 在 （1） 没有发生的时候，primes[j] * i 的最小质因子一定是 primes[j]，此时 i 还没找到自己的最小质因子
        	// （3）所有合数都有自己的最小质因子，所以一定会被筛
          for (int j = 0; primes[j] <= n / i; j++) {
              st[primes[j] * i] = true;
              if (i % primes[j] == 0) break;
          }
      }
  }
  

分解质因数

• 分解质因数

  void divide(int n) {
      for (int i = 2; i <= n / i; i++) {
          if (n % i == 0) { // 此时 i 一定是质数
              int cnt = 0;
              while (n % i == 0) {
                  cnt++;
                  n /= i;
              }
              // 有 cnt 个 i
              printf("%d %d\n", i, cnt);
          }
      }
      // 大于 sqrt(n) 的数
      if (n > 1) printf("%d 1\n", n);
      puts("");
  }
  

约数

基本定理：任何一个大于 11 的自然数 NN ，如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积 $N=P^{a_1}_1P^{a_2}_2P^{a_3}_3......P^{a_n}_n$，这里 $P_1<P_2<P_3......<P_n$ 均为质数，其中指数 $ai$ 是正整数。

• 约数个数：$(a_1 + 1) * (a_2 + 1)* ... * (a_n + 1)$
• 约数之和：$(P_{1}^{0}+P_{1}^{2}+…+P_{1}^{a1})∗…∗(P_{n}^{0}+P_{n}^{2}+…+P_{n}^{a1})$

// n 个正整数 ai, 请你输出这些数的乘积的约数个数
#include <iostream>
#include <unordered_map>

using namespace std;

const int m = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n--) {
        int k;
        cin >> k;
        for (int i = 2; i <= k / i; i++) {
            while (k % i == 0) {
                primes[i]++;
                k /= i;
            }
        }
        if (k > 1) primes[k]++;
    }
    long long ans = 1;
    for (auto[k, v] : primes) ans = ans * (v + 1) % m;
    cout << ans << endl;
    return 0;
}

// n 个正整数 ai，请你输出这些数的乘积的约数之和，
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n--) {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i++)
            while (x % i == 0) {
                x /= i;
                primes[i]++;
            }

        if (x > 1) primes[x]++;
    }

    LL res = 1;
    for (auto p : primes) {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b--) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

最大公约数

** 欧几里得算法** 又称辗转相除法，是指用于计算两个非负整数非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式 $gcd(a,b) = gcd(b,a MOD b)$。

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法：用来求 $a*x + b * y = (a, b)$ 的 x、y 的解，其中 $(a,b)$ 是 $gcd(a, b)$, 为了表示简单，记为 $d$

通解为 ： $ x = x_0 + k * (b / d)$ 、$y =y_0 + k * (a/d) $

代码实现

LL exgcd(LL a, LL b, LL& x, LL& y) {
    if(b == 0) {
        y = 0, x = 1;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

证明如下图：