数论
质数
从 2 开始的整数定义的,小于等于 1 的数既不是质数也不是合数。
在大于 1 的整数中,如果只包含 1 和这个数本身两个约数,就被称为质数 或者叫素数。
质数的判定
试除法
如果 d ∣ n d|n d ∣ n ,那么 n d ∣ n \frac{ n }{ d }|n d n ∣ n ,只枚举每对约数中些较小那个的数,令 d ≤ n d d \le \frac{ n }{ d } d ≤ d n ,解得 d ≤ n d \le \sqrt{n} d ≤ n 。
从 2 一直枚举到 n \sqrt{n} n ,时间复杂度:O ( n ) O(\sqrt{n}) O ( n )
1 2 3 4 5 6 7 8 9 10 bool is_prime (int n) { if (n<2 ) return false ; for (int i=2 ;i<=n/i;i++) { if (n%i==0 ) { return false ; } } return true ; }
试除法判定质数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> using namespace std;bool is_prime (int n) { if (n<2 ) return false ; for (int i=2 ;i<=n/i;i++) { if (n%i==0 ) return false ; } return true ; } int main () { int n; cin >> n; while (n--) { int a; cin >> a; if (is_prime (a)) cout << "Yes" << endl; else cout << "No" << endl; } return 0 ; }
分解质因数
分解质因数
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 28 #include <iostream> using namespace std;int n, a;void divide (int n) { for (int i=2 ;i<=n/i;i++) { if (n%i==0 ) { int s = 0 ; while (n%i==0 ) { s++; n/=i; } cout << i << " " << s << endl; } } if (n>1 ) cout << n << " " << 1 << endl; } int main () { cin >> n; while (n--) { cin >> a; divide (a); cout << endl; } return 0 ; }
质数筛
质数定理:1 ~ n 中大约有 n ln n \frac{n}{\ln n} ln n n 个质数。
埃氏筛法时间复杂度:O ( n ⋅ log log n ) O(n \cdot \log\log n) O ( n ⋅ log log n )
线性筛法时间复杂度:O ( n ) O(n) O ( n )
筛质数的原理:如果 p 没有被筛掉,说明在之前 2 ~ p-1 的过程中都没有把 p 筛掉,说明 p 不是 2 ~ p-1 的倍数,2 ~ p-1 都不是 p 的约数,因此 p 是质数。
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <iostream> using namespace std;const int N = 1e6 +10 ;int prime[N], cnt;bool st[N];void get_primes (int n) { for (int i = 2 ; i <= n; i++) { if (!st[i]) prime[cnt++] = i; for (int j = i+i; j <= n; j += i) st[j] = true ; } } void get_primes (int n) { for (int i = 2 ; i <= n; i++) { if (!st[i]){ prime[cnt++] = i; for (int j = i; j <= n; j += i) st[j] = true ; } } } #include <iostream> using namespace std;const int N = 1e6 +10 ;int primes[N];int cnt;int st[N];void get_primes (int n) { for (int i=2 ;i<=n;i++) { if (!st[i]) primes[cnt++] = i; for (int j=0 ;primes[j]<=n/i;j++) { st[primes[j]*i] = true ; if (i%primes[j]==0 ) break ; } } } int main () { int n; cin >> n; get_primes (n); cout << cnt << endl; }
约数
试除法求一个数的所有约数
试除法求约数
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 28 29 #include <iostream> #include <algorithm> using namespace std;vector<int > get_divisors (int n) { vector<int > res; for (int i=1 ;i<=n/i;i++) { if (n%i==0 ) { res.push_back (i); if (i!=n/i) res.push_back (n/i); } } sort (res.begin (), res.end ()); return res; } int main () { int n; cin >> n; while (n--) { int a; cin >> a; auto t = get_divisors (a); for (auto x: t) cout << x << " " ; cout << endl; } return 0 ; }
约数个数
如果一个数 N = p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k N=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \dotsm p_k^{\alpha_k} N = p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k
因为每个约数可以记作 d = p 1 β 1 ⋅ p 2 β 2 ⋯ p k β k d=p_1^{\beta_1}\cdot p_2^{\beta_2} \dotsm p_k^{\beta_k} d = p 1 β 1 ⋅ p 2 β 2 ⋯ p k β k
β 1 , β 2 , … , β k \beta_1,\beta_2,\dotsc,\beta_k β 1 , β 2 , … , β k 是一种取法,根据乘法原理
N 的约数的个数为 ( α 1 + 1 ) ⋅ ( α 2 + 1 ) ⋯ ( α k + 1 ) (\alpha_1+1) \cdot (\alpha_2+1) \dotsm (\alpha_k+1) ( α 1 + 1 ) ⋅ ( α 2 + 1 ) ⋯ ( α k + 1 )
int 范围内,一个数的约数最多有 1500 ~ 1600 个
约数之和
约数之和公式:( p 1 0 + p 1 1 + ⋯ + p 1 α 1 ) ⋅ ( p 2 0 + p 2 1 + ⋯ + p 2 α 2 ) ⋅ ⋯ ⋅ ( p k 0 + p k 1 + ⋯ + p k α k ) (p_1^{0}+p_1^{1}+\dotsb+p_1^{\alpha_1}) \cdot (p_2^{0}+p_2^{1}+\dotsb+p_2^{\alpha_2}) \cdot \dots \cdot (p_k^{0}+p_k^{1}+\dotsb+p_k^{\alpha_k}) ( p 1 0 + p 1 1 + ⋯ + p 1 α 1 ) ⋅ ( p 2 0 + p 2 1 + ⋯ + p 2 α 2 ) ⋅ ⋯ ⋅ ( p k 0 + p k 1 + ⋯ + p k α k )
约数之和
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 28 29 30 31 32 33 #include <iostream> #include <unordered_map> using namespace std;typedef long long LL;const int 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, a]: primes) { LL t = 1 ; while (a--) { t = (t*p+1 )%mod; } res = (res * t)%mod; } cout << res << endl; return 0 ; }
欧几里得算法(辗转相除法)求最大公约数
最大公约数
最小公倍数:[a, b] = a*b/(a, b)
最小公倍数 = 两数之积除以最小公约数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <iostream> using namespace std;int gcd (int a, int b) { return b ? gcd (b, a%b):a; } int n;int main () { cin >> n; while (n--) { int a, b; cin >> a >> b; cout << gcd (a,b) << endl; } return 0 ; }
欧拉函数
1 ~ N 中与 N 互质的数的个数被称为欧拉函数 ,记为 ϕ ( N ) \phi(N) ϕ ( N ) 。
若在算数基本定理中:N = p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k N=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \dotsm p_k^{\alpha_k} N = p 1 α 1 ⋅ p 2 α 2 ⋯ p k α k
欧拉函数的计算公式:ϕ ( N ) = N ⋅ ( 1 − 1 p 1 ) ⋅ ( 1 − 1 p 2 ) ⋯ ( 1 − 1 p k ) \phi(N)=N \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \dotsm (1 - \frac{1}{p_k}) ϕ ( N ) = N ⋅ ( 1 − p 1 1 ) ⋅ ( 1 − p 2 1 ) ⋯ ( 1 − p k 1 )
容斥原理证明:
从 1 ~ N 中去掉所有 p 1 , p 2 , … , p k p_1, p_2, \dotsc, p_k p 1 , p 2 , … , p k 的倍数。
N − N p 1 − N p 2 − N p 3 − ⋯ − N p k N-\frac{N}{p_1}-\frac{N}{p_2}-\frac{N}{p_3}-\dotsb-\frac{N}{p_k} N − p 1 N − p 2 N − p 3 N − ⋯ − p k N
由于去除的数可能是 p 1 ⋅ p 2 , … , p i ⋅ p j , … p_1 \cdot p_2, \dotsc, p_i \cdot p_j, \dotso p 1 ⋅ p 2 , … , p i ⋅ p j , … 的倍数,所以要把多去除的数加回来。
+ N p 1 ⋅ p 2 + N p 1 ⋅ p 3 + N p 1 ⋅ p 4 + ⋯ + N p i ⋅ p j + ⋯ +\frac{N}{p_1 \cdot p_2}+\frac{N}{p_1 \cdot p_3}+\frac{N}{p_1 \cdot p_4}+\dotsb+\frac{N}{p_i \cdot p_j}+\dotsm + p 1 ⋅ p 2 N + p 1 ⋅ p 3 N + p 1 ⋅ p 4 N + ⋯ + p i ⋅ p j N + ⋯
同样,那些 p 1 ⋅ p 2 ⋅ p 3 , … , p i ⋅ p j ⋅ p k , … p_1 \cdot p_2 \cdot p_3, \dotsc, p_i \cdot p_j \cdot p_k, \dotso p 1 ⋅ p 2 ⋅ p 3 , … , p i ⋅ p j ⋅ p k , … 同时是三个质因子倍数的数,会被第一步减去三次,又被第二步加回三次,所以需要再在这里去掉一次。
− N p 1 ⋅ p 2 ⋅ p 3 − N p 1 ⋅ p 2 ⋅ p 4 − N p 1 ⋅ p 2 ⋅ p 5 − ⋯ − N p i ⋅ p j ⋅ p k − ⋯ -\frac{N}{p_1 \cdot p_2 \cdot p_3}-\frac{N}{p_1 \cdot p_2 \cdot p_4}-\frac{N}{p_1 \cdot p_2 \cdot p_5}-\dotsb-\frac{N}{p_i \cdot p_j \cdot p_k}-\dotsm − p 1 ⋅ p 2 ⋅ p 3 N − p 1 ⋅ p 2 ⋅ p 4 N − p 1 ⋅ p 2 ⋅ p 5 N − ⋯ − p i ⋅ p j ⋅ p k N − ⋯
⋯ \dotsm ⋯
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> using namespace std;int main () { int n; cin >> n; while (n--) { int a; cin >> a; int res = a; for (int i=2 ;i<=a/i;i++) { if (a%i==0 ) { res = res /i*(i-1 ); while (a%i==0 ) a/=i; } } if (a>1 ) res=res/a*(a-1 ); cout << res << endl; } return 0 ; }
欧拉定理:若 a 与 n 互质,则 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)} \equiv 1 \pmod {n} a ϕ ( n ) ≡ 1 ( m o d n ) 。
费马小定理:如果 a 与 p 互质,且 p 是质数,那么:a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod {p} a p − 1 ≡ 1 ( m o d p )
快速幂
快速求解 a k m o d p a^{k} \bmod p a k m o d p 的结果。
时间复杂度 O ( log k ) O(\log k) O ( log k )
快速幂求逆元
考察快速幂和小费马定理。
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 28 29 30 31 #include <iostream> using namespace std;typedef long long LL;int pmi (int a, int k, int p) { int res = 1 ; while (k) { if (k&1 ) res = (LL)res*a%p; k>>=1 ; a = (LL)a * a % p; } return res; } int main () { int n; scanf ("%d" , &n); while (n--) { int a, p; scanf ("%d%d" , &a, &p); int res = pmi (a, p-2 , p); if (a % p) printf ("%d\n" , res); else puts ("impossible" ); } return 0 ; }
扩展欧几里得算法
裴蜀定理:对任意正整数 a,b,一定存在非零整数 x,y 使得 ax + by = gcd(a, b)。
扩展欧几里得算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> using namespace std;int exgcd (int a, int b, int &x, int &y) { if (!b) { x = 1 , y = 0 ; return a; } int d = exgcd (b, a%b, y, x); y -= a/b*x; return d; } int main () { int n; scanf ("%d" , &n); while (n--) { int a, b, x ,y; scanf ("%d%d" , &a, &b); exgcd (a, b, x, y); printf ("%d %d\n" , x, y); } return 0 ; }
线性同余方程
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 #include <iostream> using namespace std;typedef long long LL;int exgcd (int a, int b, int & x, int & y) { if (!b) { x=1 ,y=0 ; return a; } int d = exgcd (b, a%b, y, x); y -= a/b*x; return d; } int main () { int n; scanf ("%d" , &n); while (n--) { int a, b, m; scanf ("%d%d%d" , &a, &b, &m); int x, y; int d = exgcd (a, m, x, y); if (b%d) puts ("impossible" ); else printf ("%d\n" , (LL)x*(b/d)%m); } }
中国剩余定理
m 1 , m 2 , … , m k m_1, m_2, \dotsc, m_k m 1 , m 2 , … , m k 两两互质
有线性方程组
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a k ( m o d m k ) \begin{cases}
x \equiv a_1 \pmod {m_1}\\
x \equiv a_2 \pmod {m_2}\\
\vdots\\
x \equiv a_k \pmod {m_k}
\end{cases} ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎧ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a k ( m o d m k )
记
M = m 1 ⋅ m 2 ⋯ m k M=m_1 \cdot m_2 \dotsm m_k M = m 1 ⋅ m 2 ⋯ m k
M i = M m i M_i=\frac{M}{m_i} M i = m i M
M i − 1 M_i^{-1} M i − 1 表示 M i M_i M i 模 m i m_i m i 的逆。
则通解为:x = a 1 ⋅ M 1 ⋅ M 1 − 1 + a 2 ⋅ M 2 ⋅ M 2 − 1 + ⋯ + a k ⋅ M k ⋅ M k − 1 x=a_1 \cdot M_1 \cdot M_1^{-1}+a_2 \cdot M_2 \cdot M_2^{-1}+\dotsb+a_k \cdot M_k \cdot M_k^{-1} x = a 1 ⋅ M 1 ⋅ M 1 − 1 + a 2 ⋅ M 2 ⋅ M 2 − 1 + ⋯ + a k ⋅ M k ⋅ M k − 1