1 质数

定义

大于1整数中，如果只包含1和本身，这两个约数，就被称为质数（素数）

质数的判定（试除法）O(sqrt(n))

最大为 n / i

  1. for (int i = 2; i <= n / i; i++) {
  2.     if (n % i ==0) 
  3.         return false;
  4. }

分解质因数（试除法）O(sqrt(n))

  1. for (int i = 2; i <= n / i; i++) {
  2.     if (n % i ==0) {
  3.         int s = 0;
  4.         while (n % i == 0) {
  5.             n /= i;
  6.             s++;
  7.         }
  8.         System.out.println(i +" "+ s)
  9.     }   
  10. }

筛质数

（埃氏筛法） O(nloglogn)

  1. for (int i = 0; i <= n; i++) {
  2.     if (st[i] != 0) {
  3.         prime[cnt++] = n;
  4.         for (int j = i + i;j <= n; j += i) st[j] = ture;
  5.     }
  6. }

线性筛法
image.png

  1. for (int i = 0; i <= n; i++) {
  2.     if (st[i] != 0) {
  3.         prime[cnt++] = n;
  4.         for (int j = 0; primes[i] <= n / i; j += i) {
  5.             st[primes[j] * i] = true;
  6.              if (i % primes[j] == 0) break;
  7.         }
  8.     }
  9. }

2 约数

约数的判定（试除法）

约数的个数

image.png

约数之和

image.pngimage.png

最大公约数 O(logn)

欧几里得算法（辗转相除法）
image.png

  1. int gcd(int a, int b) {
  2.     return b ? gcd(b, a % b) : a;
  3. }

3 欧拉定理

定义

1~N 中与 N 互质的个数
image.png
image.png

  1. for (int i = 2; i <= a / i; i++) {
  2.     if (a % i == 0) {
  3.         res = res / i * (i - 1);
  4.         while (a % i == 0) a /= i;
  5.     }
  6. }
  7. if (a > 1) res = res /a * (a -1);

筛法求欧拉函数

求1 - n 中所有的数的欧拉函数

  1. private static long get_eulers(int n) {
  2.         for (int i = 2; i <= n; i++) {
  3.             if (st[i] == false) {
  4.                 primes[cnt++] = i;
  5.                 phi[i] = i - 1;
  6.             }
  7.             for (int j = 0; primes[j] <= n / i; j++) {
  8.                 st[primes[j] * i] = true;
  9.                 if (i % primes[j] == 0) {
  10.                     phi[primes[j] * i] = phi[i] * primes[j];
  11.                     break;
  12.                 }
  13.                 phi[primes[j] * i] = phi[i] * (primes[j] - 1);
  14.             }
  15.         }
  16.         long res = 0;
  17.         for (int j = 1; j <= n; j++) {
  18.             res += phi[j];
  19.         }
  20.         return res;
  21.     }

4 快速幂

快速求出来，image.png

  1. res = 1;
  2. while (k != 0) {
  3.     if (k & 1) res = res * a % p;
  4.     k >>= 1;
  5.     a = a * a % p
  6. }

5 扩展欧几里得
image.png

image.png

6 求解线性同余方程

image.png