---
title
Toán và số học
---

Toán và số học
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Tầm quan trọng của toán học trong tin học
* Có thể nói toán học là khởi nguồn của tin học, mọi chương trình, trang web, tất cả những gì chúng ta tiếp cận được qua internet đều được thành hình từ những bài toán mà các nhà phát triển đã giải quyết để giờ đây chúng ta thỏa mái sử dụng chúng.
* Toán học trong Lập trình thi đấu giúp ta xử lý tối ưu bài toán nhất có thể. Giỏi toán là một lợi thế lớn đối với những người theo Lập trình thi đấu. Chẳng hạn với bài toán điển hình tính $1+2+3+...n$, nếu làm thông thường thì ta sẽ dùng 1 vòng `for` để xử lý với độ phức tạp $O(n)$. Tuy nhiên, nếu ta nháp và thu được công thức toán học $1+2+3+...+n= \frac{n\cdot(n+1)}{2}$ thì bây giờ độ phức tạp của ta chỉ là $O(1)$.
* Đối với lập trình thi đấu của chúng ta, sự quan trọng này còn được nâng cao khi ta phải giải các bài toán bằng những thuật toán, công thức toán chính xác và tối ưu. Vì thế, hôm nay chúng mình sẽ giới thiệu cho các bạn một vài phép toán được sử dụng rất thường xuyên trong lập trình thi đấu.

# GCD/LCM
## 1. GCD (Ước chung lớn nhất)
* GCD (hay ước chung lớn nhất) của hai số $a$ và $b$ là phép toán mà chúng ta sẽ tìm ra số lớn nhất mà hai số $a$ và $b$ đều chia hết.
### Thuật toán cơ bản
* Ý tưởng thuật toán: Chúng ta thấy rằng $\gcd(a, b) \le \min(a, b)$, vì thế ta có thể tìm $\gcd$ của $a$ và $b$ bằng cách chạy từ $\min(a, b)$ xuống $1$, giá trị đầu tiên là ước của cả $a$ và $b$ là $\gcd$ cần tìm.
:::spoiler **Code mẫu:**

#include <bits/stdc++.h> 

using namespace std;

int main()
{
    int a, b;   // Khai báo hai biến a và b
    cin >> a >> b; //Nhập a và b
    int gcd;   // Khai báo biến chứa kết quả
    int chay = min(a,b);  // Tìm giá trị nhỏ nhất của a và b để bắt đầu chạy
    for (int i = chay; i >= 1; i--)
    {  
          if (a % i == 0 && b % i == 0)
          {  // Nếu a và b đều chia hết cho đang chạy tới, lưu lại đáp án rồi dừng vòng lặp 
             gcd = i;
             break;
          }
    }
    
    cout << gcd;  // Xuất kết quả
    return 0;
}

:::
* Vì chúng ta chạy từ $\min(a,b)$ đến 1 nên độ phức tạp thuật toán của sẽ là $\min(a,b)$, nếu số lớn hơn $10^9$, thuật toán của không thể chạy được. Do đó, chúng ta sẽ giảm độ phức tạp của bài toán bằng cách áp dụng thuật toán Euclid.

### Thuật toán Euclid
* Thuật toán hoạt động dựa trên 2 tính chất:
:::success
- $\gcd(a, 0)=\gcd(0, a)=a$ với $a ≠ 0$
- Nếu $m$ là số nguyên bất kỳ, thì $gcd(a + m*b, b) = gcd(a, b)$ hay nói cách khác $gcd(a, b)=gcd(a \ \text{mod} \ b, b)$
:::

* Tính chất $1$ là trường hợp cơ sở của thuật toán [Euclid](https://en.wikipedia.org/wiki/Euclidean_algorithm#:~:text=In%20mathematics%2C%20the%20Euclidean%20algorithm%2C%20%5Bnote%201%5D%20or,described%20it%20in%20his%20Elements%20%28c.%20300%20BC%29.), tính chất $2$ giúp ta chia nhỏ bài toán lớn, phức tạp thành bài toán nhỏ, dễ giải hơn.
* Theo đó, ta có thể lấy $a = a \% b$, hoán đổi hai số (vì số dư luôn bé hơn số chia) và lặp lại cho đến khi phần dư bằng $0$ thì ta sẽ tìm được $\gcd$ của $a$ và $b$. Vì thế, độ phức tạp của thuật toán giờ đây chỉ còn là $O(\log \text{min}(a, b))$, nên chúng ta có thể áp dụng với những số có giá trị bé hơn hoặc bằng $10^{18}$.
#### **Code mẫu:**
:::spoiler **Đệ quy**

long long gcd (long long a, long long b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

:::
:::spoiler **Khử đệ quy**

long long gcd (long long a, long long b)
{
    int tmp;
    while (b != 0)
    {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

:::
\
Ngoài ra, trong thư viện `algorithm` có hàm tính $\gcd$ bằng câu lệnh: `__gcd(a, b)` với a và b là hai số cần tìm giá trị gcd.

**Ví dụ:**

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a = 100, b = 35;
    cout << __gcd(a, b); //5
    
    return 0;
}

## 2. LCM (Bội chung nhỏ nhất)
* LCM (hay bội chung nhỏ nhất) là số nhỏ nhất có thể chia hết cho hai số $a$ và $b$.
### Thuật toán cơ bản
* Ý tưởng thuật toán: Chúng ta có thể thấy ở trường hợp tệ nhất, bội chung của hai số $a$ và $b$ sẽ là $a \times b$ nên chúng ta sẽ nhân $a$ với số chạy từ $1$ cho đến $b$, nếu kết quả cũng chia hết cho $b$ thì ta sẽ nhận kết quả đó làm đáp án.
:::spoiler **Code mẫu:**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long a, b;  // Khai báo, nhập a và b
    cin >> a >> b;
    
    long long ans;
    for (int i = 1; i <= b; ++i)
    {   // Chạy từ 1 đến b rồi nhân với b để tìm đáp án
        if (a * i % b == 0)
        {
            ans = a * i;   
            break;
        }
    }
    cout << ans;  // Xuất đáp án
    return 0;
}

:::
* Thuật toán này cũng sẽ chỉ làm được với những số bé hơn khoảng $10^8$ do độ phức tạp sẽ là $O(\min(a,b))$.
### Thuật toán cải tiến
* LCM có 1 tính chất đó là:
:::info
$\gcd(a, b) \times \text{lcm} (a, b) = a \times b ⇔ \text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$
:::
* Khi áp dụng tính chất này, độ phức tạp sẽ được giảm còn $O(\log \min(a, b))$ nếu ta sử dụng thuật toán Euclid cho $\gcd(a,b)$.
:::spoiler **Code mẫu:**

#include <bits/stdc++.h>

using namespace std;

long long gcd (long long a, long long b)
{    // Tìm GCD bằng thuật toán Euclid
    int tmp;
    while (b != 0)
    {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

long long lcm (long long gcd, long long a, long long b)
{  // Tìm LCM
    return a * b / gcd;
}
// Lưu ý là do hàm lcm có thể bị tràn số nên đôi khi cần cách làm khác

int main()
{
    long long a, b;   
    cin >> a >> b;
    cout << lcm(gcd(a, b), a, b); // Xuất đáp án
    return 0;
}

:::
# Số nguyên tố
* Số nguyên tố là số nguyên lớn hơn $1$ và có đúng $2$ ước là $1$ và chính nó.
* Ví dụ:
- Số $5$ là số nguyên tố là $5$ chỉ chia hết cho $1$ và $5$.
- Số $4$ không phải là số nguyên tố vì số $4$ có thể chia được cho $1, 2, 4$.
## Thuật toán cơ bản
- Để kiểm tra số $n$ có phải là số nguyên tố hay không, chúng ta chỉ cần chạy từ $2$ đến $n-1$ (vì số nguyên tố sẽ chia được cho $1$ và chính nó), nếu có số nào có giá trị từ $2$ đến $n-1$ mà $n$ có thể chia hết thì số $n$ không phải là số nguyên tố, còn nếu $n$ không chia hết cho số nào thì $n$ chính là số nguyên tố.
:::spoiler **Code mẫu:**

#include <bits/stdc++.h> 

using namespace std;

bool isPrime(int n)
{   // Kiểm tra n có phải số nguyên tố không
    for (int i = 2; i <= n - 1; i++)
        if (n % i == 0) return false;
        // Nếu n chia hết cho số i đang chạy thì số đó không phải là số nguyên tố
    return true;
}

int main()
{
    int n;
    cin >> n;
    if (isPrime(n) == true)  // Xuất đáp án
       cout << "Day la so nguyen to";
    else
       cout << "Day khong phai la so nguyen to";
    return 0;
}

:::
- Vì duyệt từ $2$ đến $n-1$ nên độ phức tạp của thuật toán sẽ là $O(n)$, nên chỉ có thể chạy được với $n$ dưới $10^7$.
## Thuật toán cải tiến
* Chúng ta có nhận xét sau:
* Giả sử $n$ là hợp số ⟹ ta có thể biểu diễn $n = a × b$ với $a, b$ là ước dương của $n$.
* Giả sử: $1 \leq a \leq b$ ⟹ $a × a \leq a × b = n$ ⟹ $1 \leq a \leq \sqrt{n}$ (với $a$ là $1$ ước dương của $n$).
* Vì thế thay vì duyệt hết từ $1$ đến $n$, thì chúng ta chỉ cần duyệt từ $1$ đến $\sqrt{n}$ để kiểm tra số đó có phải là số nguyên tố hay không.
:::spoiler **Code mẫu:**

#include <bits/stdc++.h> 

using namespace std;

bool isPrime(int n)
{   // Kiểm tra n có phải số nguyên tố không
    for (int i = 2; i <= (int)sqrt(n); i++)
        if (n % i == 0) return false;
        // Nếu n chia hết cho số i đang chạy thì số đó không phải là số nguyên tố
    return true;
}

int main()
{
    int n;
    cin >> n;
    if (isPrime(n) == true)  // Xuất đáp án
       cout << "Day la so nguyen to";
    else
       cout << "Day khong phai la so nguyen to";
    return 0;
}

:::
# Sàng nguyên tố

- Sàng nguyên tố (tên tiếng là Sieve of Eratosthenes) là một thuật toán được sử dụng cho việc tìm tất cả các số nguyên tố trong đoạn $[1; n]$ trong độ phức tạp $O(n \cdot\log (\log n))$.

## 1. Thuật toán cơ bản
- Ý tưởng thuật toán:
+ Xét các số từ $i$ từ $2$ đến $n$, ta sẽ đánh dấu lại các vị trí mà các số là bội của $i$ hay các số có ước là $i$ và nhỏ hơn $n$ : $2i$, $3i$,...
+ Những số nào không được đánh dánh sẽ là số nguyên tố

Các bạn có thể xem ví dụ sau với đoạn $[1, 120]$ :

:::spoiler **Code mẫu**

const int MAX = 1000000; //Thay đổi hằng số tùy thuộc vào đề
bool isPrime[MAX + 1];

void sieve(int n)
{
    //Quy ước nếu isPrime[i] là true thì i là số nguyên tố, ngược lại thì không
    
    //Gán giá trị các số trong đoạn [2, n] là số nguyên tố
    for (int i = 2; i <= n; ++i) isPrime[i] = true;
    
    //Lặp qua i rồi duyệt qua các bội của i và đánh dấu chúng không phải số nguyên tố
    for (int i = 2; i <= n; ++i)
        for (int j = 2 * i; j <= n; j += i)
            isPrime[j] = false;
}

:::

- Để ý rằng đến đây độ phức tạp của thuật toán chưa đạt hiệu quả cao như $O(n \log (\log n))$, lúc này độ phức tạp của ta đang là $[\frac{n}{2}]+[\frac{n}{3}]+[\frac{n}{4}]+...+[\frac{n}{n}] = O(n \log n)$ với $[x]$ là phép lấy phần nguyên của số $x$.

:::success
:::spoiler **Chứng minh độ phức tạp O(n.log(n))**.
Ta có các đẳng thức/bất đẳng thức sau:

$\frac{1}{1}=1$
$\frac{1}{2}+\frac{1}{3}<\frac{1}{2}+\frac{1}{2}=1$
$\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}<\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}=1$
$\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{11}+\frac{1}{12}+\frac{1}{13}+\frac{1}{14}+\frac{1}{15}<\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=1$
....

+ Mỗi lần ta nhóm lại lần lượt $1, 2, 4, 8, ..., 2^k$ phần tử từ $1$ đến $n$ với $k \leq \log_2(n)$
+ Suy ra : $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} \leq \log_2(n)$
+ Từ đó ta được : $n(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}) \leq n \log_2(n)$
+ Cuối cùng ta có : $[\frac{n}{2}]+[\frac{n}{3}]+[\frac{n}{4}]+...+[\frac{n}{n}] \leq n \log_2(n)$
:::

- Để có thể khiến sàng của ta đạt đến sự tối ưu nhất, ta cần có vài nhận xét để tối ưu thuật toán.

## 2. Thuật toán tối ưu
- **Tối ưu 1** : Quay lại về tính chất ước của một số nguyên dương $x$ bất kì, ta chỉ cần duyệt từ $2$ đến $\sqrt{x}$ xem có tồn tại só chia hết cho $x$ không. Trong sàng nguyên tố cũng vậy, ta chỉ cần duyệt từ $2$ đến $\sqrt{n}$ thay vì $n$ để kiểm lọc các số bội của $i$.
- **Tối ưu 2** : Nếu $p$ là số nguyên tố và $p$ là ước của $i$ (với $i$ khác $p$) thì chắc chắn rằng ta đã duyệt qua các số trước có ước là $i$ hay cũng có ước là $p$ nên ta chỉ cần duyệt qua những vị trí ta xét tới và là số nguyên tố (VD khi xét $i=10$, ta không cần xét lại $10$ vì ta đã xét các số bội của $10$ hay nói cách khác là bội của số nguyên tố $2$ và $5$).
- **Tối ưu 3** : Giả sử ở $i$, ta cần phải duyệt qua bội của $i$ là $2i, 3i, 4i, ...$ ta nhận thấy rằng do ta đã đánh $2i, 3i, 4i, ... (i-1)i$ nên ta chỉ cần bắt đầu duyệt đánh dấu từ $i^2$.

:::spoiler **Code mẫu:**

const int MAX = 1000000;
bool isPrime[MAX + 1];

void sieve (int n)
{
    for (int i = 2; i <= n; ++i) isPrime[i] = true;
    
    //duyệt đến sqrt(n)
    for (int i = 2; i * i <= n; ++i)
        if (isPrime[i] == true) //Kiểm tra i có phải số nguyên tố 
            for (int j = i * i; j <= n; j += i) //duyệt từ i^2
                isPrime[j] = false;
}

:::

- Do chứng minh về độ phức tạp $O(n \log \log n)$ cần sử dụng nhiều tính chất phức tạp và rắc rối nên tụi mình sẽ không trình bày ở đây để tránh gây loãng kiến thức, nếu muốn đọc thêm bạn có thể tham khảo [Chứng minh của cp-algorithms.com](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html#asymptotic-analysis).

## 3. Ứng dụng
- Sàng nguyên tố ngoài việc kiểm tra tính nguyên tố của nhiều số trong một đoạn còn có thể sử dụng để xử lý các bài toán về ước số/bội số.

### Bài toán 1 : Tính số ước số của nhiều số trong một đoạn

**Phân tích :**
- Để tính số ước của một số $x$, ta sẽ có 2 thuật toán cơ bản sau:
+ Duyệt qua từ $1$ đến $x$ đếm những số nào chia hết cho x. Độ phức tạp : $O(x)$.
+ Duyệt qua từ $1$ đến $\sqrt{x}$ cộng 2 lần vào đáp án với những số chia hết chia hết cho $x$ trong đoạn đó. Độ phức tạp : $O(\sqrt{x})$ (Lưu ý là với số chính phương thì phải trừ 1 vào đáp án do lúc này tồn tại $u$ sao cho $u \times u=x$).

- Ta thấy rằng 2 thuật toán này chưa đạt đến hiệu quả cao với xử lý nhiều số cùng một lúc. Vậy nên ta cần tối ưu bước tính này bằng Sàng. Giả sử $cnt_i$ là số ước của $i$, với Sàng, ta cũng có 2 cách xử lý:
+ Duyệt $x$ từ $1$ đến $n$ và cộng 1 vào bội số của số $x$. Độ phức tạp $O(n \log n)$.
+ Thấy rằng với mọi số tự nhiên $a$, luôn tồn tại cặp $(x, y)$ thỏa $a=x \times y$, nên giả sử $x \leq y$, bây giờ thay vì đếm cả $x$ lẫn $y$, thì ta chỉ cần đếm $x$ và ta sẽ luôn tìm được $y$ còn lại, tức ta sẽ cộng $2$ một lúc thay vì $1$ ở thuật toán trên. Duyệt $k$ từ $1$ đến $\sqrt{n}$, ta sẽ chỉ cộng $1$ vào **số chính phương** $k \times k$, và ta sẽ cộng 2 với những bội số $k$ lớn hơn $k \times k$ còn lại. độ phức tạp : $O(n \log \log n)$.

:::spoiler **Code mẫu Cách 1:**

const int MAX = 1000000;
int cnt[MAX + 1];

void sieve(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        //bội của i bắt đầu từ i và không vượt quá n
        for (int j = i; j <= n; j += i)
        {
            cnt[j] += 1;
            //cộng 1 vào số ước vào các bội của i 
        }
    }
}

:::

:::spoiler **Code mẫu Cách 2:**

const int MAX = 1000000;
int cnt[MAX + 1];

void sieve(int n)
{
    for (int i = 1; i * i <= n; ++i)
    {
        cnt[i * i] += 1;
        //ta chỉ cộng một vào số chính phương, vì i*i chỉ có một ước phân biệt là i
        
        //ta bắt đầu duyệt từ i*(i+1)
        for (int j = i * (i + 1); j <= n; j += i)
        {
            cnt[j] += 2;
            //Giải thích cộng 2 :
            //với (i + 1) * i có hai ước phân biệt là y = i + 1 và x = i
            //với (i + 2) * i có hai ước phân biệt là y = i + 2 và x = i
            //với (i + 3) * i có hai ước phân biệt là y = i + 3 và x = i
            //...
        }
    }
}

:::

\
**Mở rộng:** Ngoài ra ta còn có một tính chất là :
- Giả sử ta phân tích thừa số nguyên dương $N$ như sau : $N=p_1^{q_1} \times p_2^{q_2} \times p_3^{q_3} \times ... \times p_k^{q_k}$ (với $p_1, p_2, ..., p_k$ là các số nguyên tố phân biệt và $q_1, q_2, ..., q_k$ là các số nguyên không âm).
- Lúc này **số ước số** của $N$ bằng $(q_1+1) \times (q_2+1) \times \ ... \ \times (q_k+1)$.
- Giả sử $N=20$, phân tích thừa số nguyên tố $20=2^2 \times 5$, lúc này số ước số của $N$ là $(2+1) \times (1+1) = 6$ bao gồm {$1, 2, 4, 5, 10, 20$}.

### Bài toán 2 : Phân tích thừa số nguyên tố của nhiều số trong một đoạn

**Phân tích :**
- Trong bài toán này, ta có thể xử lý số $x$ với độ phức tạp $O(\sqrt{x})$. Tuy nhiên độ phức tạp này thật sự không hiệu quả, nên ta cần phải có cách nhanh hơn.
- Giả sử ta cần phân tích số nguyên dương $N=p_1^{q_1} \times p_2^{q_2} \times p_3^{q_3} \times ... \times p_k^{q_k}$ (với $p_1, p_2, ..., p_k$ là các số nguyên tố phân biệt và $q_1, q_2, ..., q_k$ là các số nguyên không âm).
- Không mất tính tổng quát, ta giả sử $p_1<p_2<...<p_k$, ta sẽ tìm và lần lượt duyệt qua từng thừa số nguyên tố nhỏ nhất của từng số trong đoạn $[1, n]$.
- Ta gọi trong hàm Sàng của ta $smallestPrime_i$ là thừa số nguyên tố nhỏ nhất của $i$. Ý tưởng và cài đặt của ta cũng sẽ tương tự như thuật $O(n \log \log n)$ của Sàng.

:::spoiler **Code mẫu:**

const int MAX = 1000000;
int smallestPrime[MAX + 1];

void sieve(int n)
{
    // khởi gắn những giá trị thừa số nguyên tố nhỏ nhất của i
    for (int i = 1; i <= n; ++i) smallestPrime[i] = i;
    
    for (int i = 2; i * i <= n; ++i)
        if (smallestPrime[i] == i)
        //Khi thừa số nguyên tố nhỏ nhất của i là chính nó    
        //Đồng nghĩa với việc i chính là số nguyên tố
            for (int j = i * i; j <= n; j += i)
            {
            //Ta duyệt qua các bội số của số nguyên tố i bắt đầu từ i^2 
            //Vì ta đã đánh gán thừa số nguyên tố nhỏ nhất các số 2i, 3i, 4i, ... (i-1)i
                smallestPrime[j] = i;
            }
}

void factorize(int x)
{
    while(x > 1)
    { //Lặp khi x>1
        cout << smallestPrime[x] << ' '; 
        //xử lý thừa số nguyên tố nhỏ nhất của x hiện tại
        x /= smallestPrime[x];
        //chia đi thừa số nguyên tố nhỏ nhất của x hiện tại 
    }
}
/*
VD : x = 100 = 2*2*5*5
output smallestPrime[100] : 2
output smallestPrime[50] : 2
output smallestPrime[25] : 5
output smallestPrime[5] : 5

output : 2 2 5
*/

:::

# Đồng dư thức
- Đến với Đồng dư thức, ta sẽ làm việc với phép toán chia lấy phần dư hay phép modulo (Trong C++ ký hiệu là ``%``). Trong các bài toán sử dụng modulo, hầu hết **những giá trị thật** khi không lấy modulo trong bài toán thường sẽ rất lớn và dễ gây tràn số lẫn bộ nhớ. VD với $m=17$, thay vì ta làm việc với $233$ thì ta sẽ xử lý với $233 \ \text{mod 17}=12$.

- Một số tính chất cần lưu ý của Đồng dư thức $(m>1)$:
1. Phép cộng : $(a+b) \ \text{mod m} \equiv ((a \ \text{mod m}) + (b\ \text{mod m}))\ \text{mod m}$.
2. Phép trừ : $(a-b) \ \text{mod m} \equiv ((a \ \text{mod m}) - (b\ \text{mod m}) + m)\ \text{mod m}$ (Lưu ý với phép trừ, nếu kết quả ra âm thì thông thường với hầu hết các bài toán, ta cần phải cộng kết quả cho $m$)
3. Phép nhân : $(a \times b) \ \text{mod m} \equiv ((a \ \text{mod m}) \times (b \ \text{mod m})) \ \text{mod m}$.
4. Phép mũ : $a^n \ \text{mod m} \equiv (a \ \text{mod m})^n \ \text{mod m}$.
5. Phép chia : Do có nhiều tính chất phức tạp và kỹ thuật khó trong phép chia có modulo nên tụi mình sẽ không trình bày thêm. Các bạn có thể tham khảo ***Nghịch đảo modulo*** ở [Series số học của HackerEarth được dịch lại trên VNOI Wiki](https://vnoi.info/wiki/Home#series-s%E1%BB%91-h%E1%BB%8Dc-c%E1%BB%A7a-hackerearth).
6. Nếu $a \equiv b \ \text{mod m}$ thì $(a-b) \equiv 0 \ \text{mod} \ m$.

- Ngoài ra còn nhiều những tính chất khác cũng hay không kém, tuy nhiên ở đây tụi mình sẽ không liệt kê được hết, mọi người có thể tham khảo thêm ở phần Divisibily và Modular Arithmetics ở [Number Theory : Structure, Examples and Problems by Andreescu, Andric](https://blngcc.files.wordpress.com/2008/11/andreescu-andrica-problems-on-number-theory.pdf).

- Lưu ý nhỏ : Với những bài toán sử dụng modulo, cần xử lý kỹ các bước modulo để tránh bị tràn số kiểu dữ liệu `int` hay `long long`. Các bạn có thể tham khảo thêm ở [Tổng hợp kinh nghiệm thi HSGQG của anh Trần Xuân Bách](https://vnoi.info/wiki/algo/skill/Kinh-nghiem-thi-VOI.md#tr%C3%A0n-s%E1%BB%91).
# Bài tập
## Bài 1
**Đề bài:** Cho 2 số nguyên dương $N, P$. Tìm số nguyên không âm $M$ lớn nhất sao cho $P^M$ là ước của $N!$ (ký hiệu $x!$ là $x$ **giai thừa** hay bằng $1 \times 2 \times 3 \times... \times x$).
**Dữ liệu đề bài đảm bảo luôn tìm được nghiệm**.

**INPUT:**
- 1 dòng duy nhất chứa là hai số nguyên dương $N$ và $P$ $(\leq 30.000)$.

**OUTPUT:**
- 1 dòng duy nhất là số $M$ lớn nhất thỏa điều kiện.

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 7 3 | 2 |

- Giải thích : $7!=1 \times 2 \times 3 ... \times 7=5.040, P^2=9$ chia hết cho $5.040$. Giả sử $M=3$ thì $P^3=27$ không chia hết cho $5.040$.

(Nguồn : [VNOJ](https://oj.vnoi.info/problems/))

## Bài 2
**Đề bài:** Một số nguyên dương được gọi là **phong phú** nếu tổng các ước số không kể chính nó lớn hơn số đó. Ví dụ $12$ có tổng ước số không kể chính nó là $1+2+3+4+6=16>12$. Do đó $12$ là một số phong phú. Đếm xem trong đoạn $[L, R]$ có bao nhiêu số phong phú.

**INPUT:**
- 1 dòng duy nhất gồm hai số $L, R$ $(1 \leq L \leq R \leq 10^6)$.

**OUTPUT**
- 1 dòng duy nhất gồm số lượng số phong phú trong đoạn $[L, R]$.

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 1 50 | 9 |

- Giải thích : các số phong phú trong đoạn $[1, 50]$ là $12, 18, 20, 24, 30, 36, 40, 42, 48$.

(Nguồn : [VNOJ](https://oj.vnoi.info/problems/))

## Bài 3
**Đề bài:** Cho một dãy số nguyên không âm $a$ gồm $N$ phần tử (trong đó có ít nhất 2 giá trị phân biệt). Tìm tất cả số nguyên dương $M$ sao cho $a_1 \ \text{mod} \ M = a_2 \ \text{mod} \ M = a_3 \ \text{mod} \ M = ... = a_N \ \text{mod} \ M$

**INPUT:**
- Dòng đầu là số nguyên dương $N$ $(2 \leq N \leq 10^6)$
- Dòng tiếp theo là $N$ số nguyên không âm $a_i$ $(\leq 10^9)$

**OUTPUT:**
- Dòng đầu tiên là số lượng số $M$ thỏa mãn
- Dòng tiếp theo là các số $M$ thỏa mãn theo thứ tự bất kì

**VD:**
| INPUT | OUTPUT |
| -------- | -------- |
| 5 | 2 |
| 4 13 16 10 7 | 1 3|

- Giải thích:
- Với $M=1$, ta có $N$ số trong test đề dư $0$ nên $M=1$ thỏa điều kiện
- Với $M=3$, ta có $N$ số trong test đề dư $1$ nên $M=3$ thỏa điều kiện
- Giả sử $M=5$, ta có $4 \ \text{mod} \ 5 = 4$, $13 \ \text{mod} \ 5 = 3$, $16 \ \text{mod} \ 5 = 1$, $10 \ \text{mod} \ 5 = 0$, $7 \ \text{mod} \ 5 = 2$ gồm nhiều giá trị khác nhau nên $M=2$ không thỏa mãn

(Nguồn : Đề thi tuyển sinh lớp 10 chuyên tin Sở Giáo dục và Đào tạo TP.HCM năm 2022)

# Mở rộng : Sàng trên đoạn, Số chính phương, Sàng chính phương, ...
- Sàng nguyên tố nói riêng và số học nói chung còn có nhiều biến thế. Tùy thuộc vào cách ta cài đặt và tư duy của ta, ta có thể xử lý các bài toán từ những bước cơ bản nhất cho phù hợp với dữ kiện đề bài. Điều này khiến số học là một trong những phần Toán học quan trọng nhất đối với Lập trình thi đấu.
- Do dung lượng bài viết cũng như đây là những kiến thức ngoài bài viết nên tụi mình sẽ để lại những link hay và không trình bày ở đây nhé. Lưu ý, do những bài viết ở đây dành cho Lập trình thi đấu chung nên sẽ bao gồm cả những kiến thức rất khó, các bạn có thể chỉ cần quan tâm những kiến thức cần thiết nhé.

- Tổng hợp các link bài viết hữu ích :
+ [Các kỹ thuật cơ bản trên Sàng của cp-algorithms](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)
+ [Sàng tuyến tính $O(n)$](https://cp-algorithms.com/algebra/prime-sieve-linear.html)
+ [Nhiều ứng dụng hơn của Sàng như tính : phi hàm euler, tích ước số, ...](https://codeforces.com/blog/entry/54090)
+ [Một vài kiến thức về đại số của cp-algorithms](https://cp-algorithms.com/algebra/binary-exp.html)
+ [Series số học của HackerEarth được VNOI dịch lại](https://vnoi.info/wiki/Home#series-s%E1%BB%91-h%E1%BB%8Dc-c%E1%BB%A7a-hackerearth)

# Tài liệu Tham khảo
:::info
[[1] https://blngcc.files.wordpress.com/2008/11/andreescu-andrica-problems-on-number-theory.pdf](https://blngcc.files.wordpress.com/2008/11/andreescu-andrica-problems-on-number-theory.pdf)
[[2] https://vnoi.info/wiki/Home#series-số-học-của-hackerearth](https://vnoi.info/wiki/Home#series-số-học-của-hackerearth)
[[3] https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)
[[4] https://usaco.guide/gold/modular](https://usaco.guide/gold/modular)
:::