---
tags: Note
title: Đại số
author: CppCodingClub
license: Public Use
---
:::info
:::spoiler Table of contents
[TOC]
:::
# QUAN TRỌNG: KIẾN THỨC CẦN NHỚ KHI ĐI THI
## Tổng, tích, số lượng ước số
### Định lý thừa số nguyên tố
Đối với mỗi số n > 1 chỉ có duy nhất 1 cách triển khai thừa số nguyên tố
$$n = p^{e_1}_1 * p^{e_2}_2 * ... p^{e_k}_k$$
- Trong đoạn. từ 1 --> 1e9 thì các SNT cách nhau không quá 300
### Phân tích thừa số nguyên tố
```cpp=
void phantich(int n){
for (int i = 2; i * i <= n; i++){ // duyệt tới căn n thôi vì có thể tìm ra ước đối | căn n * căn n = n
while(n%i==0){
cout << i << ' ';
n /= i;
}
}
if(n > 1) // trường hợp n là số nguyên tố nên sẽ không bị chia trong điều kiện
cout << n;
}
```
[Tham khảo :book:](https://blog.28tech.com.vn/c-phan-tich-thua-so-nguyen-to)
### Tính số lượng ước
- Gọi $p$ là các thừa số nguyên tố của $n$, ta có:
$$n = p^{e_1}_1 * p^{e_2}_2 * ... p^{e_k}_k$$
- Ta có công thức của tổng số ước như sau:
$$d(n) = (e_1+1)*(e_2+1)* ... * (e_k+1)$$
- VD: $80 = 2^4*5^1$
$=> d(80) = (4+1) * (1+1) = 5 * 2 = 10$
### Tính tổng các ước
$$𝜎(n) = \frac{p_1^{e_1+1} - 1}{p_1 - 1} * \frac{p_2^{e_2+1} - 1}{p_2 - 1} * ... *\frac{p_k^{e_k+1} - 1}{p_k - 1}$$
VD:
$84 = 2^2 * 3^1 * 7^1$
$\sigma(84) = \frac{2^{3} - 1}{2 - 1} \cdot \frac{3^{2} - 1}{3 - 1} \cdot \frac{7^{2} - 1}{7 - 1} = 7 \cdot 4 \cdot 8 = 224$
:::spoiler Chứng minh
Để tìm được tổng ước của n, ta cần tổng ước của từng số nhân với nhau ra tổ hợp
$S = 1 + p + p^2 + ... + p^k$
$p*S = p + p^2 + p^3 + ... + p^{k+1}$
$pS - S = (p + p^2 + \dots + p^{k+1}) - (1 + p + p^2 + \dots + p^k)$
$pS - S = p^{k+1} - 1 \Rightarrow S(p - 1) = p^{k+1} - 1 \Rightarrow S = \frac{p^{k+1} - 1}{p - 1}$
:::
### Tính tích các ước
$$M(n) = n^{d(n)/2}$$
*Note: d(n) là số lượng ước số của n
- Giải thích: Áp dụng số cặp số ước để tính
- VD: Tổng các ước của 12
- 12 có các ước sau: 1,2,3,4,6,12
- Ta chia theo cặp
| Các cặp| Tích mỗi cặp |
| -------- | -------- |
| $1 * 12$ | $12$ |
| $2*6$ | $12$|
| $3*4$ | $12$ |
=> Tích các cặp đều là 12
- Số cặp = ${\frac{1}{2}}$ số lượng ước | do mỗi cặp có 2 số
=> Tích các ước = $12^{số-cặp}$ = $12^3$ = $1 728$
- Trường hợp đặc biệt nếu cặp lẻ
VD: $25 = 5^2$
--> $M(n) = n^{3/2} = \sqrt[2]{25^3} = \sqrt[2]{15625} = 125$
## Cấp số cộng, nhân
### Cấp số cộng
- Dạng tổng quát của cấp số cộng:
$$u_1,u_1+2d,u_1+3d,...,u_1+(n-1)d$$
> $u_1$: số hạng đầu
$d$: công sai (hệ số)
$n$: số số hạng
- Cách tính công sai:
+ lấy số liền kề sau - số hiện tại
+ $d = \frac{u_n-u_1}{n-1}$ (dựa trên công thức tính số hạng thứ $n$)
- Tính số hạng thứ $n$: $u_n = u_1 + (n-1)d$
- Tìm số khi biết 2 số liền kề: $$u_k = \frac{u_{k+1} - u_{k-1}}{2}$$
hay
$$u_{k+1} - u_{k-1} = 2u_k$$
- Tổng cấp số cộng:
$$\frac{n*(u_1 + u_n)}{2}$$
> Giống công thức của Gauss
hay ta có thể thay $u_n = u_1 + (n-1)d$
$$\frac{n*(2u_1 + (n-1)d)}{2}$$
thu gọn lại là
$$n*u_1 + \frac{n*(n-1)}{2}d$$
### Cấp số nhân
- Dạng tổng quát của cấp số nhân:
$$u_1,u_1*q,u_1*q^2,...,u_1*q^{n-1}$$
> $u_1$: số hạng đầu
$d$: công bội (hệ số)
$n$: số số hạng
- Cách tính công bội $p$:
+ $q = \frac{u_{k+1}}{u_k}$
- Tính số hạng thứ $n$: $u_n = u_1 * q^{n-1}$
- Tìm số khi biết 2 số liền kề: $$(u_k)^2 = u_{k+1}*u_{k-1}$$
:::spoiler Chứng minh
$(u_k)^2 = (u_{k-1}*q)^2 =$ ==$(u_{k-1})^2 * q^2$==
$u_{k-1}*u_{k+1} = u_{k-1}*(u_{k-1}*q^2) =$ ==$(u_{k-1})^2 * q^2$==
:::
hay (như công thức tính $u_n$)
$$u_{k} = u_1 * q^{k-1}$$
- Tổng cấp số nhân:
$$S_n = \frac{u_1*(1 - q^n)}{1- q}$$
:::spoiler Chứng minh
$S_n = u_1 + u_1*q + u_1*q^2 +... + u_1*q^{n-1}$
$q*S_n = u_1*q + u_1*q^2 + u_1*q^3 +...+ u_1*q^n$
$S_n - q*S_n = (u_1 + u_1*q + u_1*q^2 +... + u_1*q^{n-1}) - (u_1*q + u_1*q^2 + u_1*q^3 +...+ u_1*q^n)$
$S_n - q*S_n = u_1 - u_1*q^n$
$S_n(1-q) = u_1(1 - q^n)$
$S_n = \frac{u_1(1-q^n)}{1-q}$
:::
hay ta có thể nhân tử và mẫu với $-1$
$$S_n = \frac{-u_1*(1-q^n)}{-(1-q)}$$
thu gọn lại là
$$S_n = \frac{u_1*(q^n-1)}{q-1}$$
:::spoiler Chứng minh
$S_n = u_1 + u_1*q + u_1*q^2 +... + u_1*q^{n-1}$
$q*S_n = u_1*q + u_1*q^2 + u_1*q^3 +...+ u_1*q^n$
$q*S_n - S_n = (u_1*q + u_1*q^2 + u_1*q^3 +...+ u_1*q^n) - (u_1 + u_1*q + u_1*q^2 +... + u_1*q^{n-1})$
$q*S_n - S_n = u_1*q^n - u_1$
$S_n(q-1) = u_1(q^n - 1)$
$S_n = \frac{u_1(q^n-1)}{q-1}$
:::
## Fermat nhỏ
## Lý thuyết số của anh Triệu
# I. Lý thuyết số
**[Tham khảo 👍](https://vallicon.com/post/l%C3%BD-thuy%E1%BA%BFt-s%E1%BB%91-(number-theory)-lNWMYl1E7vr)**
## I.A. Số nguyên tố
### I.A.0 - Số nguyên dương
- ==Là tập hợp các số tự nhiên lớn hơn 0, ký hiệu: $Z+$==
### I.A.1 - Số nguyên tố
- ==Là số > 1 và **CHỈ** chia hết cho chính số đó và số 1==
- VD: 3,5,7,11,...
### I.A.2 - Hợp số
- ==Là số tự nhiên có nhiều hơn 2 ước và > 1==
- VD: số 4 có các ước số {4,2,1}. => 4 là hợp số
### I.A.3 - Số ngoài số nguyên tố và hợp số
- **Số 0** có vô số ước
- **Số 1** chỉ có 1 ước là chính nó
- **Số âm**
### I.A.4 - Ước số
- ==Ước số là số được chia hết bởi một số==
- VD: 2 là ước của 4 do 4 chia hết cho 2 (4 % 2 = 0)
### I.A.5 - Ước số nguyên tố
- ==Là ước của một số mà vừa phải là số nguyên tố==
- VD: ƯSNT của 12 có {3}.
### I.A.6 - Nhân tử của một phép nhân các số với nhau
- ==Nhân tử là các số hoặc biểu thức được nhân với nhau trong một phép nhân. Khi hai hay nhiều số được nhân với nhau, mỗi số đó được gọi là một nhân tử của phép nhân.==
- VD: a x b x c = d => a,b,c là nhân tử của d.
### I.A.7 - Phân tích thừa số nguyên tố
- ==Là tách một số tự nhiên thành các thừa số nguyên tố nhỏ nhất có thể của nó và thừa số nguyên tố đó <= n==
- VD: 2 x 3 = 6. => 2,3 là thừa số nguyên tố của 6
- **Cách phân tích: chia n lần lượt cho các số nguyên tố và đếm số ước có được cho đến khi không còn chia hết được nữa.**
[VD cách phân tích :computer:](https://vietjack.com/toan-lop-6/bai-15-phan-tich-mot-so-ra-thua-so-nguyen-to.jsp)
### I.A.8 - Đếm số ước số của một số nguyên dương
- ==Ta phải lấy số mũ của từng thừa số nguyên tố riêng biệt + 1 rồi nhân với nhau==
- VD: 60 = 2^2^ x 3^1^ x 5^1^
+ Số lượng ước số của 60: (2+1) x (1+1) x (1+1) = 3 x 2 x 2 = 12
**[Nguồn :information_source:](https://rdsic.edu.vn/blog/toan/dem-so-luong-uoc-so-cua-so-nguyen-duong-n-bi-quyet-don-gian-va-hieu-qua-vi-cb.html)**
### I.A.9 - Sàng nguyên tố
- ==Đây là một phương pháp để kiểm tra số nào là số nguyên tố trong khoảng từ 2 -> n==
- Được phát minh bởi nhà toán học Hy Lạp Cổ Đại, ông loại bỏ các số chia hết cho các số nhỏ nhất ngoại trừ chúng còn sót lại cho đến số $\sqrt{n}$. Các số còn lại sẽ là số nguyên tố.
#### Thuật toán C++ phổ biến nhất áp dụng sàng nguyên tố
:::spoiler Nguồn
[Wikipedia :book:](https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes)
[Kteam :star:](https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes)
:::
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n;
bool mark[MAX_INT];
bool isPrime(int num){
for(int i = 2 ; i * i <= num ; ++i)
if(num % i == 0) return 0;
return 1;
}
int main(){
cin >> n;
for(int i = 2 ; i <= n ; ++i)
if(!isPrime(i)) mark[i] = 1;
// Kết thúc vòng lặp, nếu mark[x] == 0 thì x là số nguyên tố và ngược lại
}
```
**Độ phức tạp: $O(n * \sqrt{n})$**
#### Để tối ưu hoá độ phức tạp, ta có thể làm như sau
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n;
bool mark[MAX_INT];
int main(){
cin >> n;
for(int i = 2 ; i * i <= n ; ++i)
if(!mark[i])
for(int j = 2 ; i * j <= n ; ++j) mark[i * j] = 1;
// Kết thúc vòng lặp, nếu mark[x] == 0 thì x là số nguyên tố và ngược lại
// Duyệt các bội số
}
```
**Độ phức tạp: $O(n * log(logn))$**
### Định lý thừa số nguyên tố
Đối với mỗi số n > 1 chỉ có duy nhất 1 cách triển khai thừa số nguyên tố
$$n = p^{e_1}_1 * p^{e_2}_2 * ... p^{e_k}_k$$
### Phân tích thừa số nguyên tố
```cpp=
void phantich(int n){
for (int i = 2; i * i <= n; i++){ // duyệt tới căn n thôi vì có thể tìm ra ước đối | căn n * căn n = n
while(n%i==0){
cout << i << ' ';
n /= i;
}
}
if(n > 1) // trường hợp n là số nguyên tố nên sẽ không bị chia trong điều kiện
cout << n;
}
```
[Tham khảo :book:](https://blog.28tech.com.vn/c-phan-tich-thua-so-nguyen-to)
### Tính số lượng ước
- Gọi $p$ là các thừa số nguyên tố của $n$, ta có:
$$n = p^{e_1}_1 * p^{e_2}_2 * ... p^{e_k}_k$$
- Ta có công thức của tổng số ước như sau:
$$d(n) = (e_1+1)*(e_2+1)* ... * (e_k+1)$$
- VD: $80 = 2^4*5^1$
$=> d(80) = (4+1) * (1+1) = 5 * 2 = 10$
### Tính tổng các ước
$$𝜎(n) = \frac{p_1^{e_1+1} - 1}{p_1 - 1} * \frac{p_2^{e_2+1} - 1}{p_2 - 1} * ... *\frac{p_k^{e_k+1} - 1}{p_k - 1}$$
VD:
$84 = 2^2 * 3^1 * 7^1$
$\sigma(84) = \frac{2^{3} - 1}{2 - 1} \cdot \frac{3^{2} - 1}{3 - 1} \cdot \frac{7^{2} - 1}{7 - 1} = 7 \cdot 4 \cdot 8 = 224$
### Tính tích các ước
$$M(n) = n^{d(n)/2}$$
> d(n) là số lượng ước số của n
- Giải thích: Áp dụng số cặp số ước để tính
- VD: Tổng các ước của 12
- 12 có các ước sau: 1,2,3,4,6,12
- Ta chia theo cặp
| Các cặp| Tích mỗi cặp |
| -------- | -------- |
| $1 * 12$ | $12$ |
| $2*6$ | $12$|
| $3*4$ | $12$ |
=> Tích các cặp đều là 12
- Số cặp = ${\frac{1}{2}}$ số lượng ước | do mỗi cặp có 2 số
=> Tích các ước = $12^{số-cặp}$ = $12^3$ = $1 728$
- Trường hợp đặc biệt nếu cặp lẻ
VD: $25 = 5^2$
--> $M(n) = n^{3/2} = \sqrt[2]{25^3} = \sqrt[2]{15625} = 125$
### Ước tính số lượng số nguyên tố từ $1 \rightarrow n$
$$\pi(n) \approx \frac{n}{ln(n)-1}$$
### Tìm số lần xuất hiện của thừa số nguyên tố $p$ trong $n!$ (Legendre)
$$\nu_i(n!) = \Sigma_{i = 1}^{\infty} \lfloor \frac{n}{p_i} \rfloor$$
### Tìm $C^N_K (\mod M)$ với $M <= 10^7$ và $M$ là số nguyên tố (Lucas)
Ta có: $\begin{cases}
N = n_0*M^0 + n_1*M^1 + ... + n_p*M^p \\
K = k_0*M^0 + k_1*M^1 + ... + k_p*M^p
\end{cases}$
$$C^K_N = \prod^p_{i = 0} C^{K_i}_{N_i}$$
### Tìm $C^K_N (\mod M)$ với $M <= 10^6$ (Lucas + Legendre)
$$C_N^K = p^{v_p(N!) - v_p(K!) - v_p((N-K)!)} \cdot \frac{f(N)}{f(K) \cdot f(N-K)} \pmod{p^a}$$
Trong đó:
- $\nu_i(n!)$: số mũ của $p$ trong $n!$ (tính bằng Legendre)
- $f(n)$: tích tất cả các số từ $1 \rightarrow n$ không chia hết cho $p$, lấy dư cho $p^a$
## I.B Các phép tính
### Modulo
#### Cách lấy phần dư không dùng ký hiệu `%`
:::success
:brain: Mô phỏng não của Quân chia lấy dư như nào
:::
- VD: 41 và 5
- Quân thấy rằng $5*9 = 40$ sát với $41$ (lấy từ ước lượng/bảng cửu chương) => $41%40$ = 1
- Vậy từ đâu mà Quân ước lượng ra $5$ phải nhân với bao nhiêu để ra số nhỏ hơn và sát nhất với số $41$? --> Quân phải ước lượng số gần $41$ mà có thể chia hết cho 5 (có đuôi $0$ hoặc $5$) đó là số $40$, vậy từ đâu Quân có số $9$ để nhân vào với $5$? --> Quân lấy $40/5$
:::success
:mag: Phân tích
:::
- gọi $(\frac{a}{b})$ là $c$ --> để ==kiếm $c$ phù hợp sao cho $c*b =$ số nguyên gần nhất nhỏ hơn $a$== (tiền vị) ==do phép chia nguyên chỉ lấy phần nguyên==, ví dụ như $16/5$ = 3.2 --> chỉ lấy phần nguyên: 3 (phép này còn gọi là hàm `floor`)
- sau đó ta lấy $b*(\frac{a}{b})$ --> có được số nguyên gần nhất $\leq$ $a$
- Cuối cùng lấy $a$ $-$ số nguyên gần nhất $\leq$ $a$ = số dư của phép tính
:::success
:1234: Toán học
:::
Từ VD trên, ta có công thức:
==$$a - b*(\frac{a}{b})$$==
---
### Sàng nguyên tố
```cpp=
vector<int> sieve(int n) {
vector<bool> sang(n + 1, true);
sang[0] = sang[1] = false;
for (int i = 2; i * i <= n; i++) {
if (sang[i]) {
for (int j = i * i; j <= n; j += i) {
sang[j] = false;
}
}
}
return sang
}
```
---
### Đồng dư
- Gọi là $a$ đồng dư $b$ ($mod$ $n$) khi $a$ % $n = b$ % $n$ hoặc $|a-b|$ % $n = 0$
$a \equiv b$ $\pmod{n}$
## I.C Các loại số
### Số chính phương
- Là số tự nhiên $n$ có $\sqrt{n} \in \mathbb{N}$
# II. Công thức / Thuật toán / Quy Luật
## II.A Toán học
### Tổng của n số hạng đầu:
==$(n(u1+un))/2$==
==số số hạng(tổng của cặp số)/2==
> n = số lượng số
> u1 = số đầu
> un = số cuối
> u1/un = tổng mỗi cặp số
:::info
VD tổng của cặp số:
1+2+3+...+100
cặp 1: (1+100) = 101
cặp 2: (2+99) = 101
cặp 3: (3+98) = 101
...
:::danger
=> Tổng của mỗi cặp số đơn giản là: ==(đầu + đuôi)== :100:
:::
---
### Tìm ƯCLN
```cpp=
// Bình thường
int a,b;
int UCLN;
if(a == 0 || b == 0){
UCLN = a+b;
}
while(a*b != 0){
if(a > b){
a = a % b; // or a = a/b
}
else{
b = b % a; // or b = b/a
}
}
UCLN = a + b;
// Đệ Quy
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b); // a%b thay thế cho hiệu số của số lớn hơn với số nhỏ hơn
}
```
:::danger Lưu ý
Nếu gcd(a,b) mà a hoặc b là số chẵn thì gcd luôn > 2 :warning:
:::
:::info
Ước chung lớn nhất của hai số nguyên không thay đổi khi thay
số lớn hơn bằng hiệu của nó với số nhỏ hơn
[Video tham khảo :book:](https://www.youtube.com/watch?v=RvhplEKgX2g)
[Link tham khảo :book:](https://blog.28tech.com.vn/c-uoc-chung-lon-nhat-boi-chung-nho-nhat)
:::
- Nếu $gcd(a,b) = 1$ => $a$ và $b$ có chung thừa số nguyên tố
---
### Tìm BCNN
- Do ==max(a, b) <= lcm (BCNN) <= a*b== nên:
```cpp=
// Bình thường
int LCM(int a, int b){}
int maxV = a*b;
for(int i = max(a, b); i <= maxV; i++){
if(i % a == 0 && i % b == 0){
return i;
}
}
}
// Đệ Quy
int LCM(int a, int b) {
return a / gcd(a, b) * b; // để khỏi bị tràn số khi a*b
}
```
:::info
$$BCNN(a,b) = \frac{a*b}{GCD(a,b)}$$
:::
---
### Tìm khoảng tuyến đường giữa 2 điểm trong ma trận (khoảng cách Manhattan)
Để đi từ $A$ đến $B$ theo phương cách tuyến đường, ta cần cần:
- Di chuyển theo trục $x$ từ $x_1$ đến $x_2$
- Di chuyển theo trục $y$ từ $y_1$ đến $y_2$
--> Do đó khoảng cách bằng tổng khoảng cách di chuyển của chúng
```yaml!
Ví dụ, khoảng cách Manhattan giữa hai điểm: P1 có tọa độ (x1, y1) và điểm P2 có
tọa độ (x2, y2)
```
$$|x_1 - x_2| + |y_1 - y_2|$$
:::success
Nói cách khác là khoảng cách Manhattan = bước đi trên trục x + bước đi trên trục y
:::
[Link tham khảo 🎓](https://vi.wikipedia.org/wiki/Kho%E1%BA%A3ng_c%C3%A1ch_Manhattan)
---
### Khoảng cách đi chéo, ngang, dọc giữa 2 điểm trong ma trận (khoảng cách chéo)
Khoảng cách đường chéo giữa 2 điểm $(x1, y1)$ và $(x2, y2)$ là:
$$max(|x_1 - x_2|, |y_1 - y_2|)$$
- **Giải thích:**
**1. Khả năng di chuyển chéo:**
- Khi bạn di chuyển chéo trong lưới ô vuông, mỗi bước di chuyển chéo có thể làm giảm đồng thời tọa độ $x$ và $y$ của bạn.
- Ví dụ, từ điểm $(0,0)$ đến điểm $(1,1)$ bạn cần một bước chéo.
**2. Số bước cần thiết:**
- Trong một lưới ô vuông, để di chuyển từ điểm $(x_1, y_1)$ đến điểm $(x_2, y_2)$, bạn cần phải tính số bước tối thiểu để thay đổi tọa độ $x$ và $y$ của bạn từ $x_1$ đến $x_2$ và từ $y_1$ đến $y_2$.
- Mỗi bước di chuyển chéo thay đổi cả hai tọa độ $x$ và $y$ cùng lúc. Do đó, số bước chéo tối thiểu cần thiết là số bước cần thiết để thay đổi tọa độ $x$ hoặc $y$ lớn nhất.
- VD đi từ $(0,0)$ đến$(3,4)$, ta đi chéo đến $(3,3)$ và đi ngang 1 ô nữa để tới $(3,4)$
**3. Công thức cụ thể:**
- $|x_1 - x_2|$ là sự thay đổi trong tọa độ $x$.
- $|y_1 - y_2|$ là sự thay đổi trong tọa độ $y$.
- Vì mỗi bước chéo giảm đồng thời cả $x$ và $y$, bạn cần đủ bước chéo để giảm giá trị lớn nhất trong số các thay đổi tọa độ $x$ và $y$.
---
### Tìm khoảng cách đường thẳng giữa 2 điểm trong trục toạ độ Oxy (khoảng cách Euclid)
Ta có điểm P có toạ độ là (x~1~, y~1~) và điểm Q có toạ độ là (x~2~, y~2~), ta có công thức
$$d(x, y) = \sqrt{(x_1 - x_2)^2 + (x_2 - y_2)^2}$$
:::success
Áp dụng Pytagore để ra công thức này
:::
---
### Nguyên lý bao hàm - loại trừ
[Wikipedia :book:](https://vi.wikipedia.org/wiki/Nguy%C3%AAn_l%C3%BD_bao_h%C3%A0m-lo%E1%BA%A1i_tr%E1%BB%AB)
[Ví dụ dễ hiểu :books:](https://viblo.asia/p/cong-thuc-bao-ham-loai-tru-3Q75wNQJlWb)
- **Cup:** Nếu $A = \{1, 2, 3\}$ và $B = \{3, 4, 5\}$, thì $A \cup B = \{1, 2, 3, 4, 5\}$
- **Cap:** Ví dụ: Nếu $A = \{1, 2, 3\}$ và $B = \{3, 4, 5\}$ , thì $A \cap B = \{3\}$
**hay đơn giản là**
:::info
Lẻ thì cộng
Chẵn thì trừ (tính theo đơn vị của 1 nhóm)
:::
**Cách áp dụng**
#### Giải thích
- **Bao hàm**: Cộng số lượng phần tử trong từng tập hợp để đảm bảo các phần tử bị đếm ít nhất một lần.
- **Loại trừ**: Trừ số lượng phần tử trong các giao nhau của hai tập hợp để loại bỏ các phần tử bị đếm trùng lặp.
- **Cộng lại**: Cộng số lượng phần tử trong các giao nhau của ba tập hợp để bù đắp cho các phần tử bị trừ nhiều lần.
- **Loại trừ lần cuối**: Trừ số lượng phần tử trong giao nhau của tất cả bốn tập hợp để loại bỏ phần tử bị đếm nhiều lần.
### Mũ phần tỉ --> căn
VD:
- 5^3/2^ = $\sqrt[2]{5^3}$
- 5^3/3^ = $\sqrt[3]{5^3}$
- 5^4/6^ = $\sqrt[6]{5^4}$
---
### Công thức tính số hoán vị
https://www.mathvn.com/2021/08/cong-thuc-tinh-so-hoan-vi-so-chinh-hop.html
## II.B Utilities
### Kiểm tra Palindrome (từ đọc xuôi hay ngược đều giống nhau)
```cpp=
bool is_Palidrome(string text){
for(int i = 0; i < text.size()/2; i++){ // từ ở giữ không cần xét
if(text[i] != text[text.size() - i - 1]){ // đối xứng
return false;
}
}
return true;
}
```
---
### Kiểm tra Pangram (string chứa tất cả alphabet)
```cpp
bool checkPangram(string& str)
{
// Create a hash table to mark the characters
// present in the string
vector<bool> mark(26, false);
// For indexing in mark[]
int index;
// Traverse all characters
for (int i = 0; i < str.length(); i++) {
// If uppercase character, subtract 'A'
// to find index.
if ('A' <= str[i] && str[i] <= 'Z')
index = str[i] - 'A';
// If lowercase character, subtract 'a'
// to find index.
else if ('a' <= str[i] && str[i] <= 'z')
index = str[i] - 'a';
// If this character is other than english
// lowercase and uppercase characters.
else
continue;
mark[index] = true;
}
// Return false if any character is unmarked
for (int i = 0; i <= 25; i++)
if (mark[i] == false)
return (false);
// If all characters were present
return (true);
}
```
[Details :bulb:](https://www.geeksforgeeks.org/pangram-checking/)
---
### Permutation loop
```cpp=
void permu(vector<int> &a, bool &ok, int n){
int i = n - 1;
while(i >= 1 && a[i] > a[i+1]){
i--;
}
if(i == 0){
ok = true;
return;
}
int j = n;
while (a[i] > a[j])
{
j--;
}
swap(a[i], a[j]);
int l = i + 1, r = n;
while (l < r){ // reverse
swap(a[l], a[r]);
l++;
r--;
}
}
```
**Nguyên lý:** KT digit không tăng dần từ n-1 --> đảo với số lớn hơn nhỏ nhất (xét từ n) --> reverse đoạn sau vị trí khác biệt mới được đổi (để sort từ bé đến lớn giúp tổng thể số nhỏ hơn) => **Quy tắc:** xử lý đoạn sau --> trước --> sau --> trước --> ...
---
### Permutation recursion
```cpp=
void next_permutation(vector<int> &a, int i = 0) {
if (i >= a.size()) {
for (int x : a) {
cout << x + 1 << " ";
}
cout << endl;
return;
}
vector<bool> visited(a.size(), false);
for (int j = 0; j < i; ++j) {
visited[a[j]] = true;
}
for (int v = 0; v < a.size(); ++v) {
if (!visited[v]) {
a[i] = v;
next_permutation(a, i + 1);
}
}
}
```
**Nguyên lý:** Nếu i = size (đủ element) --> in ra --> Kết thúc hàm | --> Đánh dấu visited dự theo i --> i đại diện cho vị trí biến đổi --> trong i biến đổi các i đằng sau nó --> mỗi v là thay đổi 1 số *visited để thế số đã bị biến mất (Do i trước thay vị trí)
**VD:** 012 (gốc) --> 011 (bị thay thế bởi i = 1 và i = 2) --> 021 (thế lại vào bằng i = 2; v = 1)
---
### Số chính phương từ khoảng L --> R
$$sqrt(R) - sqrt(L) + 1$$
VD: $sqrt(36) - sqrt(25) + 1 = 6 - 5 + 1 = 6$
Do mấy số này mũ lên sẽ ra số chính phương
# III. Lưu ý
## Modulo
1. $[(a-b)\%c + c]\%c$ luôn dương
## Chia lấy ceil
1. $(n + x - 1)/x = (n-1)/x + 1$
## Cách tính $log_a{x}$
$$log_a{x} = \frac{log(x)}{log(a)}$$
Sign in with Wallet
Connect another wallet