DSA #1 - Khái niệm số học cơ bản
Số nguyên tố
Thuật toán đơn giản
Kiểm tra xem một số có ước nằm trong đoạn $[2, \sqrt{n}]$ hay không.
Chỉ cần kiểm tra đến $\sqrt{n}$ là đủ, vì nếu một số có ước $i$ nằm trong đoạn đó, thì suy ra được số đó sẽ có một ước nữa là $\frac{n}{i}$. Giá trị tối đa của $i$ sẽ là $\sqrt{n}$.
1
2
3
4
5
6
7
8
int prime(int n)
{
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return 0;
}
}
Sàng Eratosthenes
Để sử dụng sàng Eratosthenes để sàng trên $n$ phần tử, ta cần tạo được mảng có $n+1$ phần tử.
Mô tả thuật toán:
Xem tất cả các số từ 2 đến $n$ là số nguyên tố.
Nếu $i$ là số nguyên tố, duyệt tất cả các bội số của $i$ và đánh dấu nó không phải là số nguyên tố (bắt đầu từ $\sqrt{n}$).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int prime[1000001];
void sieve()
{
for (int i = 0; i <= 1000000; i++)
{
prime[i] = 1;
}
prime[0] = prime[1] = 0;
for (int i = 2; i <= 1000; i++)
{
if (prime[i])
{
for (int j = i*i; j <= 1000000; j += i)
{
prime[j] = 0;
}
}
}
}
Phân tích thừa số nguyên tố
Duyệt từ 2 đến $\sqrt{n}$. Chia liên tục cho các số nguyên tố thuộc đoạn $[2, \sqrt{n}]$. Trong mỗi lượt duyệt, in ra số nguyên tố đó, và tiếp tục với $n = n:i$.
1
2
3
4
5
6
7
8
9
10
11
12
void primeFactorization(int n)
{
for (int i = 2; i*i <= n; i++)
{
while (n % i == 0)
{
cout << i << ' ';
n = n / i;
}
}
if (n != 1) cout << n;
}
Sàng số nguyên tố trên đoạn
Cho đoạn $[L, R]$, trả về một mảng gồm các số nguyên tố thuộc đoạn trên.
Mô tả thuật toán:
Chuẩn bị trước một mảng số nguyên tố từ 2 đến $\sqrt{R}$.
Dùng các số nguyên tố đó để đánh dấu trong đoạn $[L, R]$ theo thuật toán sàng Eratosthenes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<bool> sieve(int l, int r)
{
long long sqrtr = sqrt(r);
vector<bool> marks(sqrtr + 1, false); // dont need to pre-set primes[0] and primes[1]
vector<long long> primes;
// prepare an array of prime in [2, sqrtr]
for (long long i = 2; i <= sqrtr; i++)
{
if (!marks[i]) {
primes.push_back(i);
for (long long j = i*i; j <= sqrtr; j += i)
marks[j] = true;
}
}
// primes is the array contains prime numbers from 2 to sqrt(R).
vector<bool> isPrimes(r - l + 1, true);
for (long long i : primes)
for (long long j = max(i*i, ((l + i - 1)/i * i)); j <= r; j += i) // begin with the minimum number that more than or equal to l, and % i == 0.
isPrimes[j - l] = false; // l starts as 0, ends at l - r.
if (l == 1)
isPrimes[0] = false;
return isPrimes;
}
Đếm số ước số của một số nguyên
Cách đơn giản
Duyệt từ 1 đến $\sqrt{n}$ (với biến $i$), với mỗi $i$ khác $\sqrt{n}$, tăng biến đếm lên 2 lần, một cho $i$ và một cho $\frac{n}{i}$. Với $i$ thoả $i^2$ = $n$, biến đếm tăng lên 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int count(int n)
{
int cnt = 0;
for (int i = 1; i*i <= n; i++)
{
if (n % i == 0)
{
if (i != n / i)
cnt += 2;
else cnt++;
}
}
return cnt;
}
Thuật toán dựa trên công thức toán
Cho một số $n$ phân tích được dưới dạng:
\[n = p_1^{e_1} + p_2^{e_2} + ... + p_k^{e_k}\]Số ước số của n:
\[d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdot ... \cdot (e_k + 1)\]Phi hàm Euler
Định nghĩa: Phi hàm Euler của một số $n$, ký hiệu là $\varphi(n)$, là số lượng các số nguyên tố cùng nhau với $n$ trong đoạn $[1, n]$.
Một số tính chất của hàm phi Euler:
Nếu $p$ là số nguyên tố thì $\gcd(p, q) = 1$ với $1 \leq p < q$, do đó có $\varphi(n) = p - 1$.
Nếu $p$ là số nguyên tố và $k \geq 1$, thì có $\frac{p^k}{p} = p^{k-1}$ số từ $1..p^k$ chia hết cho $p$. Do đó ta có $\varphi({p^k}) = p^k - p^{k-1}$.
Nếu $a$ và $b$ nguyên tố cùng nhau, hay $\gcd(a, b) = 1$, ta có $\varphi(ab) = \varphi(a) \cdot \varphi(b)$.
Đối với $a$ và $b$ không nguyên tố cùng nhau, $\varphi(ab) = \varphi(a) \cdot \varphi(b) \cdot \frac{d}{\varphi(d)}$ với $d = \gcd(a, b)$.
Từ các tính chất trên, cộng thêm kiến thức về phân tích thừa số nguyên tố, ta suy ra được công thức tính phi hàm Euler:
\[p = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}\]Theo tính chất 3, ở đây $p_i$ là các số nguyên tố nên từng cặp đều là nguyên tố cùng nhau:
\[\varphi(n) = \varphi(p_1^{a_1}) \cdot \varphi(p_2^{a_2}) \cdot ... \cdot \varphi(p_k^{a_k})\] \[= (p_1^{a_1} - p_1^{a_1 - 1}) \cdot (p_2^{a_2} - p_2^{a_2 - 1}) \cdot ... \cdot (p_k^{a_k} - p_k^{a_k - 1})\] \[= p_1^{a_1} \cdot (1- \frac{1}{p_1}) \cdot p_2^{a_2} \cdot (1- \frac{1}{p_2}) \cdot ... \cdot p_k^{a_k} \cdot (1 - \frac{1}{p_k})\] \[= n \cdot (1 - \frac{1}{p_1}) \cdot (1 - \frac{1}{p_2}) \cdot ... \cdot (1 - \frac{1}{p_k})\]1
2
3
4
5
6
7
8
9
10
11
12
int phiEuler(int n) {
if (n == 0) return 0;
int ans = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans -= ans / x;
}
while (n % i == 0) n = n / i;
}
if (n != 1) ans -= ans / n;
return ans;
}
Ước chung lớn nhất với thuật toán Euclid
\[gcd(a,b) = \begin{cases} a & \text{nếu } b = 0 \\ gcd(b, a \bmod b) & \text{nếu } b \neq 0 \end{cases}\]Chứng minh:
Nếu $d$ là ước của $a$ và $b$, thì nó cũng là ước của $b - a$.
Nếu $d’$ là ước của $b$ và $b - a$, thì nó cũng là ước của $b - (b - a)$ = $a$.
Do vậy, với ba số $a$, $b$ và $a - b$, nếu một số $d$ bất kỳ là ước của một trong ba số trên thì sẽ là ước của hai số còn lại.
Tức là: \(\gcd(a, b) = \gcd(b, a - b)\)
Phép tính $a - b$ sau khi thực hiện nhiều nhất $\left\lfloor \frac{a}{b} \right\rfloor$ lần thì sẽ thoả mãn $a \leq b$. Số $a$ sau khi trừ đi $\left\lfloor \frac{a}{b} \right\rfloor$ lần $b$ thì sẽ trở thành:
\[a - b \cdot \left\lfloor \frac{a}{b} \right\rfloor = a \bmod b\]Vậy:
\[\gcd(a, b) = \gcd(b, a \bmod b)\]1
2
3
4
int gcd(int a, int b)
{
return (b ? gcd(b, a % b) : a)
}
Luỹ thừa nhị phân
Định nghĩa: Để tính $a^b$, ta có công thức sau:
\[a^b = \begin{cases} 1 & \text{nếu } b = 0 \\ \left( a^{\frac{b-1}{2}} \right)^2 \times a & \text{nếu } b \text{ lẻ} \\ \left( a^{\frac{b}{2}} \right)^2 & \text{nếu } b \text{ chẵn} \end{cases}\]Đệ quy
1
2
3
4
5
6
7
8
long long Pow(long long a, long long b) {
if (!b) return 1;
long long x = Pow(a, b / 2);
if (b % 2 == 0)
return x * x;
else
return x * x * a;
}
Không đệ quy
1
2
3
4
5
6
7
8
9
long long Pow(long long a, long long b) {
long long ans = 1;
while (b > 0){
if (b % 2) ans = ans * a;
a = a * a;
b = b / 2;
}
return ans;
}
Phép toán modulo
\[(a+b) \bmod m = (a \bmod m + b \bmod m) \bmod m\] \[(a-b) \bmod m = (a \bmod m - b \bmod m) \bmod m\] \[(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m\] \[a^b \bmod m = (a \bmod m)^b \bmod m\] \[\frac{a}{b} \bmod m = (a \cdot b^{-1}) \bmod m\]Trong đó: $b^{-1}$ là nghịch đảo modulo của $b$.
Thuật toán Euclid mở rộng
Thuật toán này dùng để viết $\gcd(a, b)$ dưới dạng tổ hợp tuyến tính: $ax + by = \gcd(a, b)$
Hay nói cách khác, thuật toán này tìm ra cặp số nguyên $(x, y)$ thoả mãn phương trình trên.
Việc cặp số nguyên $(x, y)$ trên luôn tồn tại được chứng minh theo Bổ đề Bézout.
Thuật toán này hoạt động như sau:
Khi kết thúc thuật toán Euclid để tìm ra $\gcd(a, b)$, ta có phương trình:
\[a \cdot 1 + 0 \cdot 0 = \gcd(a, b)\]Theo thuật toán Euclid, ở bước này ta có $b = 0$ và $\gcd(a, b) = a$, cặp $(x, y)$ lúc này là $(1, 0)$. Để tìm $(x, y)$ ứng với cặp $(a, b)$ lúc đầu, ta cần đi ngược lại các bước đệ quy để xem $(x, y)$ thay đổi như thế nào qua các bước biến đổi $(a, b)$ thành $(b, a \bmod b)$.
Xét hai phương trình sau:
\[ax + by = g\] \[bx_1 + (a \bmod b)y_1 = g\]Ta có thể biểu diễn phép toán $(a \bmod b)$ qua cách khác:
\[a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b\]Ta có:
\[bx_1 + (a \bmod b)y_1 = bx_1 + (a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b) \cdot y_1 = g\] \[\rightarrow g= ay_1 + bx_1 - b\cdot \left\lfloor \frac{a}{b} \right\rfloor \cdot y_1\] \[\Leftrightarrow g = ay_1 + b\cdot (x_1 - \left\lfloor \frac{a}{b} \right\rfloor \cdot y_1)\]Từ phương trình vừa tìm được, kết hợp với phương trình gốc (1):
\[\Leftrightarrow ax + by = ay_1 + b\cdot (x_1 - \left\lfloor \frac{a}{b} \right\rfloor \cdot y_1)\] \[\Leftrightarrow \begin{cases} x = y_1 \\ y = x_1 - y_1 \cdot \left\lfloor \dfrac{a}{b} \right\rfloor \end{cases}\]Vậy ta đã tìm được sự thay đổi của $(x, y)$ sau mỗi lần biến đổi từ $(a, b)$ sang $(b, a \bmod b)$ như trên.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Tra ve gia tri cua gcd(a, b), dong thoi thay doi x va y
int extendedEuclid(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = extendedEuclid(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
Nghịch đảo modulo
Định nghĩa: Nghịch đảo modulo của một số nguyên $a$ là một số nguyên $x$ thoả mãn điều kiện sau:
\[a \cdot x \equiv 1 \mod m\]Hay có cách viết khác:
\[(a \cdot x) \% m = 1\]Điều kiện: Nghịch đảo modulo $m$ của một số $a$ chỉ tồn tại khi $\gcd(a, m) = 1 $
Tìm nghịch đảo modulo sử dụng thuật toán Euclid mở rộng
Từ $\gcd(a, m) = 1$, ta suy ra được phương trình:
\[ax + my = 1\]Ta có thể tìm được cặp số nguyên $(x, y)$ thoả mãn phương trình trên bằng thuật toán Euclid mở rộng.
Phương trình trên tương đương:
\[(ax + my) \bmod m = 1 \bmod m\] \[\Leftrightarrow ((ax \bmod m) + (my \bmod m)) \bmod m = 1 \bmod m\]Mà $my \bmod m = 0$ và $1 \bmod m = 1$, tương đương:
\[\Leftrightarrow ax \bmod m = 1\]Hay có cách viết khác:
\[ax \equiv 1 \bmod m\]Vậy khi giải ra cặp số nguyên $(x, y)$ của phương trình (*) bằng thuật toán Euclid mở rộng, khi đó ta có $x$ là nghịch đảo modulo của $a$.
1
2
3
4
5
6
7
8
9
10
11
12
int modularInverse(int a, int m)
{
int x, y;
int g = extendedEuclid(a, m, x, y);
if (g != 1) {
cout << "NO SOLUTION";
return -1;
}
else {
x = (x % m + m) % m;
}
}
Tìm nghịch đảo modulo sử dụng phi hàm Euler
Ta có:
\[a^{\varphi(m)} \equiv 1 \bmod m\]Với $m$ là số nguyên tố, ta có phương trình trên tương đương:
\[a^{m-1} \equiv 1 \bmod m\]Nhân hai vế cho $a^{-1}$, ta có:
\[a^{m-2} \equiv a^{-1} \bmod m\]Vì $0 \leq a^{-1} < m$ nên:
\[a^{-1} = a^{m-2} \bmod m\]Để tính $a^{m-2} \bmod m$, ta sử dụng thuật toán luỹ thừa nhị phân, kết hợp với phép toán modulo:
\[a^b \bmod m = (a \bmod m)^b \bmod m\]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int MOD = 1e9 + 7;
long long powerMod(long long a, long long b)
{
long long ans = 1;
a %= MOD;
while (b)
{
if (b % 2 == 1) {
ans = ans * a;
ans %= MOD;
}
a = a * a;
a %= MOD;
b = b / 2;
}
return ans;
}
long long modularInverse(long long a, long long m)
{
return powerMod(a, m - 2);
}
Tổ hợp
Tính tổ hợp với n và k bé
Tính tổ hợp chập $k$ của $n$ với $0 \leq k, n \leq 1000$. Kết quả lấy dư với $10^9 + 7$.
Ta sử dụng công thức tổ hợp theo hồi quy:
\[C(n, k) = \begin{cases} 1 & \text{nếu } k = 0 \text{ hoặc } k = n \\ C(n-1, k-1) + C(n-1, k) & \text{nếu } 0 < k < n \end{cases}\]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MOD = 1e9 + 7;
int C[1000][1000]; //C[i][j]: to hop chap j cua i
void calc()
{
for (int i = 0; i < 1000; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0 || j == i)
C[i][j] = 1;
else
{
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
C[i][j] %= MOD;
}
}
}
}
Tính tổ hợp với n và k lớn
Tính tổ hợp chập $k$ của $n$ với $0 \leq k, n \leq 1000000$. Kết quả lấy dư với $10^9 + 7$.
Lúc này ta sử dụng công thức tính tổ hợp truyền thống:
\[C(n, k) = \frac{n!}{k!(n-k)!}\]Ta cần tính $C(n, k) \bmod 10^9 + 7$, tương đương với:
\[\frac{n!}{k!(n-k)!} \bmod 10^9 + 7\]Sử dụng phép toán modulo:
\[\frac{a}{b} \bmod m = (a \cdot b^{-1}) \bmod m\]Trong đó $b^{-1}$ là nghịch đảo modulo của $b$.
Ở đây, ta tạm đặt $m$ = $10^9 + 7$.
\[\Leftrightarrow (n! \cdot (k! \cdot (n - k)!)^{-1}) \bmod m\] \[\Leftrightarrow [(n! \bmod m) \cdot ((k! \cdot (n - k)!)^{-1} \bmod m)] \bmod m\]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
const int MOD = 1e9 + 7;
long long f[1000001]; // Luu giai thua cua cac so
void calcFactorial()
{
f[0] = 1;
for (int i = 1; i <= 1000000; i++)
{
f[i] = i * f[i - 1];
f[i] %= MOD;
}
}
long long powerMod(long long a, long long b)
{
long long ans = 1;
a %= MOD;
while (b)
{
if (b % 2 == 1) {
ans = ans * a;
ans %= MOD;
}
a = a * a;
a %= MOD;
b = b / 2;
}
return ans;
}
long long modularInverse(long long a, long long m)
{
return powerMod(a, m - 2);
}
void calcC(int n, int k)
{
cout << f[n] % MOD * modularInverse(f[k] * f[n - k], MOD) % MOD << endl;
}