数论

素数

1.随着数字增大，素数的出现概率变小，越来越稀疏
2.素数的数量约等于 logn

素数筛 （欧拉筛）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
using namespace std;
//求小于等于1e7的所有素数
const int n = 1e7;
//isprime用于判断某个数是否是素数
bool isprime[n + 1];
//prime用来存放找到的素数
int prime[n];
//用来记录找到的素数的总数
int cnt = 0;
int main()
{
  memset(isprime, 1, sizeof (isprime));
  for (int i = 2; i <= n; i++)
  {
    if (isprime[i])
    {
      prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
    {
      isprime[i * prime[j]] = 0;
      if (i % prime[j] == 0) break;
    }
  }
}

最大公约数与最小公倍数

gcd(a, b) * lcm(a, b) = a * b;

欧拉函数 Φ(n)

Φ(n) : 表示从 1 到 n 与 n 互质的数的个数

Φ(n) = n * (1 - 1 / p1) * (1 - 1 / p2)........(1 - 1 / pn)

当 a 和 b 互质时 Φ(a * b) = Φ(a) * Φ(b);

费马小定理

当 p 为质数，a 不为 0 时有 a^（p-1）≡ 1（mod p）

可以用来求逆元

欧拉定理

 如果 p 和 a 互质有 a ^ Φ(p) ≡ 1 (mod p)

 推论：如果 p 和 a 互质有 a ^ b ≡ a ^ (b mod Φ(p)) (mod p)

 当用费马小定理直接求逆元超限了，可以先用欧拉定理简化