Hãy xây dựng thuật toán giải bài toán sau cho số nguyên N hãy tìm tất cả các ước số của N

JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

1. Khái niệm bài toán

- Bài toán là một việc nào đó mà con người muốn máy tính thực hiện.

- Các yếu tố của một bài toán:

   + Input: Thông tin đã biết, thông tin đưa vào máy tính.

   + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính.

- Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó:

   + Input: hai số nguyên dương A, B.

   + Output: ước chung lớn nhất của A và B

2. Khái niệm thuật toán

a) Khái niệm

Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

b) Biểu diễn thuật toán

- Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành.

- Sử dụng sơ đồ khối để mô tả thuật toán. 

c) Các tính chất của thuật toán

- Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

- Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

- Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương

• Xác định bài toán

- Input: N là một số nguyên dương;

- Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″.

• Ý tưởng:

- Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N″

- Nếu N = 1 thì N không là số nguyên tố.

- Nếu 1 < N < 4 thì N là số nguyên tố.

- N ≥ 4: Tìm ước i đầu tiên > 1 của N.

+ Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N).

+ Nếu i = N thì N là số nguyên tố.

• Xây dựng thuật toán

a) Cách liệt kê

   - Bước 1: Nhập số nguyên dương N;

   - Bước 2: Nếu N=1 thì thông báo ″N không là số nguyên tố″, kết thúc;

   - Bước 3: Nếu N<4 thì thông báo ″N là số nguyên tố″, kết thúc;

   - Bước 4: i ← 2;

   - Bước 5: Nếu i là ước của N thì đến bước 7;

   - Bước 6: i ← i+1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)

   - Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc;

b) Sơ đồ khối

Lưu ý: Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.

Ví dụ 2: Sắp xếp bằng cách tráo đổi

• Xác định bài toán

   - Input: Dãy A gồm N số nguyên a1, a2,…, an

   - Output: Dãy A được sắp xếp thành dãy không giảm.

• Ý tưởng

   - Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. (Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy).

   - Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa.

• Xây dựng thuật toán

a) Cách liệt kê

   - Bước 1: Nhập N, các số hạng a1, a2,…, an;

   - Bước 2: M ← N;

   - Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp, rồi kết thúc;

   - Bước 4: M ← M – 1, i ← 0;

   - Bước 5: i ← i + 1;

   - Bước 6: Nếu i > M thì quay lại bước 3;

   - Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;

   - Bước 8: Quay lại bước 5;

b) Sơ đồ khối

Ví dụ 3: Bài toán tìm kiếm

• Xác định bài toán

- Input : Dãy A gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k (khóa)

   Ví dụ : A gồm các số nguyên ″ 5 7 1 4 2 9 8 11 25 51″ và k = 2 (k = 6).

- Output: Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 2 trong dãy là 5 (không tìm thấy 6)

• Ý tưởng

Tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết mà không tìm thấy giá trị của khóa trên dãy.

• Xây dựng thuật toán

a) Cách liệt kê

   - Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

   - Bước 2: i ← 1;

   - Bước 3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;

   - Bước 4: i ←i+1;

   - Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc;

   - Bước 6: Quay lại bước 3;

b) Sơ đồ khối

Ví dụ 4: Tìm kiếm nhị phân

• Xác định bài toán

- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k.

Ví dụ: Dãy A gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25)

- Output : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 (không tìm thấy 25)

• Ý tưởng

Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp:

   - Nếu agiữa= k thì tìm được chỉ số, kết thúc;

   - Nếu agiữa > k thì việc tìm kiếm thu hẹp chỉ xét từ adầu (phạm vi) → agiữa - 1;

   - Nếu agiữa < k việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1→acuối (phạm vi).

Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.

• Xây dựng thuật toán

a) Cách liệt kê

   - Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;

   - Bước 2: Đầu ←1; Cuối ←N;

   - Bước 3: Giữa←[(Đầu+Cuối)/2];

   - Bước 4: Nếu agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

   - Bước 5: Nếu agiữa > k thì đặt Cuối = Giữa - 1 rồi chuyển sang bước 7;

   - Bước 6: Đầu ←Giữa + 1;

   - Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên dãy, rồi kết thúc;

   - Bước 8: Quay lại bước 3.

b) Sơ đồ khối

Loigiaihay.com

Chắc hẳn, ai trong chúng ta cũng đã quá quen thuộc với bài toán đếm số ước nguyên dương của $n$. Giải thuật thông thường nhất mà mọi người thường sử dụng là giải thuật O(n),O(\sqrt{n}),O(n​), dựa trên một nhận định rằng nếu như số $n$ có một ước là i (1≤i≤n)i \ (1 \le i \le \sqrt{n})i (1≤i≤n​) thì nó cũng sẽ có một ước nữa là ni (n≤ni≤n)\frac{n}{i} \ \left(\sqrt{n} \le \frac{n}{i} \le n \right)in​ (n​≤in​≤n). Bằng phương pháp này, chúng ta có thể giải quyết mọi bài toán với giới hạn $n$ khoảng 101510^{15}1015 trở xuống (Các bạn xem lại trong chuyên đề Tìm các ước của một số nguyên).

Một phương pháp hay khác mà chúng ta cũng sử dụng là phân tích thừa số nguyên tố và đếm ước của $n$ dựa trên phân tích nguyên tố của nó. Cách làm này có thể khiến thao tác đếm ước của số $n$ giảm xuống độ phức tạp $O(\log (n))$ khi kết hợp với sàng lọc số nguyên tố, và thường được áp dụng trong các bài toán multi-testcase (các bạn xem lại trong chuyên đề Số nguyên tố). Tuy nhiên, nhược điểm của phương pháp này là bạn buộc phải tạo ra được một mảng có độ dài $n$ để đánh dấu các số nguyên tố, đồng nghĩa với việc nếu n≤109,n \le 10^9,n≤109, các bạn không thể sử dụng được nó.

Điều gì sẽ xảy ra khi chúng ta cần đếm ước của một số nguyên dương n≤1018?n \le 10^{18}?n≤1018? Phân tích thừa số nguyên tố? Không thể, vì ta không thể sàng lọc được số nguyên tố ở giới hạn này. Vậy phân tích theo phương pháp O(n)O(\sqrt{n})O(n​) truyền thống thì sao? Cũng không thể, vì O(n)≈O(109),O(\sqrt{n}) \approx O(10^9),O(n​)≈O(109), độ phức tạp này không đủ tốt. Khi đó, người ta sử dụng phương pháp đếm ước trong O(n13),O(n^{\frac{1}{3}}),O(n31​), một phương pháp rất hiệu quả nhưng lại được ít người biết đến, có lẽ vì chúng ta không thường xuyên gặp phải những bài toán như vậy. Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu ý tưởng và cách cài đặt của phương pháp này bằng C++. Trước khi đọc bài viết, các bạn cần có kiến thức đầy đủ về sàng lọc số nguyên tố, đếm ước theo phương pháp thông thường cũng như kĩ năng code ở mức khá. Nếu chưa nắm được những kiến thức này, các bạn hãy quay lại nghiên cứu những chuyên đề cũ mà mình đã để link ở trên nhé!

II. Phương pháp đếm số ước của một số trong O(n13)O(n^{\frac{1}{3}})O(n31​)

Để sử dụng được giải thuật đếm ước trong O(n13),O(n^{\frac{1}{3}}),O(n31​), trước tiên ta cần tìm hiểu về phương pháp của Fermat dùng để kiểm tra tính nguyên tố của một số. Đây là một phương pháp kiểm tra nguyên tố có tính xác suất, nghĩa là nó có thể xảy ra trường hợp sai, tuy nhiên, trong giải thuật này sự sai khác đó có thể chấp nhận được.

Ý tưởng: Phương pháp kiểm tra tính nguyên tố của Fermat được xây dựng dựa trên định lý Fermat nhỏ: Nếu $n$ là một số nguyên tố, thì với mọi giá trị $a$ sao cho $1\le a<n$

Dựa vào định lý trên, ta triển khai giải thuật như sau:

• Lấy ngẫu nhiên một số $a$ thuộc đoạn $[1,n-1]$.
• Kiểm tra đẳng thức an−1≡1 (mod n),a^{n - 1} \equiv 1 \ (\text{mod }n),an−1≡1 (mod n), nếu đẳng thức sai thì $n$ không phải là số nguyên tố, ngược lại $n$ có khả năng là một số nguyên tố.
• Lặp lại hai thao tác kiểm tra trên $k$ lần, giá trị $k$ càng lớn thì xác suất chính xác sẽ càng tăng.

Giải thuật kiểm tra tính nguyên tố của Fermat sẽ luôn luôn đúng nếu như $n$ đã là một số nguyên tố, ngược lại nó sẽ có thể sai. Tuy nhiên, như đã nói xác suất xảy ra sai khi $n$ là hợp số khá nhỏ, nên chúng ta hoàn toàn có thể sử dụng giải thuật Fermat trong một số trường hợp cụ thể. Bên cạnh đó, các bạn có thể tìm hiểu về một số giải thuật kiểm tra nguyên tố xác suất khác như Miller - Rabin hay Solovay - Strassen.

Cài đặt:

long long indian_multiplication(long long a, long long b, long long mod) { if (b == 0) return 0LL; long long half = indian_multiplication(a, b / 2LL, mod) % mod; if (b & 1) return (half + half + a) % mod; else return (half + half) % mod; } long long modular_exponentiation(long long a, long long b, long long mod) { if (b == 0) return 1LL; long long half = modular_exponentiation(a, b / 2LL, mod) % mod; long long product = indian_multiplication(half, half, mod); if (b & 1) return indian_multiplication(product, a, mod); else return product; } bool fermat_checking(long long n, int k = 50) { if (n < 4) return n == 2 || n == 3; if (n != 2 && n % 2 == 0) return false; for (int i = 1; i <= k; ++i) { long long a = 2 + rand() % (n - 3); if (modular_exponentiation(a, n - 1, n) != 1) return false; } return true; }

Giải thuật có độ phức tạp $O(k\times \log (n))$.

2. Phương pháp kiểm tra nguyên tố Miller - Rabin

Phương pháp nói trên của Fermat có ưu thế là cài đặt đơn giản, ngắn gọn, tuy nhiên xác suất sai sẽ dễ xảy ra trong trường hợp số $n$ đưa vào là một số giả nguyên tố (tức là hợp số nhưng vẫn thỏa mãn an≡1 (mod n)a^n \equiv 1 \ (\text{mod }n)an≡1 (mod n) với $a$ nào đó). Chính vì thế, khi cần tới độ chính xác cao, người ta thường sử dụng phương pháp kiểm tra tính nguyên tố Miller - Rabin, một phương pháp rất mạnh trong các phương pháp kiểm tra nguyên tố có tính xác suất.

Ý tưởng: Giải thuật Miller - Rabin được xây dựng dựa trên một số nhận định sau:

• Đối với một số chẵn $n$ bất kỳ, ta luôn luôn có thể viết nó dưới dạng n=2r×d,n = 2^r \times d,n=2r×d, với $d$ là một số lẻ và $r>0(1)$.
• Theo định lý nhỏ Fermat, nếu $n$ là một số nguyên tố, thì với mọi giá trị $a$ sao cho $1\le a<n$
• Theo bổ đề Euclid, giả sử $n$ là một số nguyên tố và $n=a\times b,$ thì chắc chắn $n$ phải chia hết cho một trong hai số $a$ hoặc $b$. Vậy nếu giả sử n=(x2−1)=(x−1).(x+1)n = (x^2 - 1) = (x - 1).(x + 1)n=(x2−1)=(x−1).(x+1) thì chắc chắn $x\equiv 1(\text{mod }n)$ hoặc $x\equiv -1(\text{mod }n)(3)$.
• Từ $(1)$ và $(2),$ ta xây dựng dãy số xk=a2k×d,∀k:0≤k≤rx_k = a^{2^k \times d}, \forall k: 0 \le k \le rxk​=a2k×d,∀k:0≤k≤r. Khi đó:

{xk=(xk−1)2;∀k:1≤k≤r.xr=an−1. (4)\begin{cases}x_k = (x_{k - 1})^2;&& \forall k: 1 \le k \le r.\\ x_r = a^{n - 1}. \end{cases} \ (4) {xk​=(xk−1​)2;xr​=an−1.​∀k:1≤k≤r. (4)

• Từ $(2)$ và $(4)$ ta có:

  xr≡1 (mod n)x_r \equiv 1 \ (\text{mod }n) xr​≡1 (mod n)

  hay

  (xr−1)2≡1 (mod n)(x_{r - 1})^2 \equiv 1 \ (\text{mod }n) (xr−1​)2≡1 (mod n)

  nên xr−1≡1 (mod n)x_{r - 1} \equiv 1 \ (\text{mod }n)xr−1​≡1 (mod n) hoặc xr−1≡−1 (mod n)x_{r - 1} \equiv -1 \ (\text{mod }n)xr−1​≡−1 (mod n). Nếu thực hiện một số hữu hạn bước như trên với các giá trị $r$ giảm dần về $0,$ thì ta có:

  • Hoặc tồn tại $k(0\le k<r)$
  • Hoặc $\forall k:0\le k<r$

Dựa vào tất cả các nhận xét trên, ta có mệnh đề kiểm tra nguyên tố Miller - Rabin như sau: Nếu $n$ là một số nguyên tố lẻ và n−1=2r×d (r>0,d mod 2≠0)n - 1 = 2^r \times d \ (r > 0, d \text{ mod }2 \ne 0)n−1=2r×d (r>0,d mod 2=0) thì $\forall a:1\le a<n,$

• Hoặc xk=a2k×d≡1 (mod n);∀k:0≤k≤rx_k = a^{2^k \times d} \equiv 1 \ (\text{mod }n); \forall k: 0 \le k \le rxk​=a2k×d≡1 (mod n);∀k:0≤k≤r.
• Hoặc $\exists k:0\le k\le r$ thỏa mãn: xk=a2k×d≡−1 (mod n)x_k = a^{2^k \times d} \equiv -1 \ (\text{mod }n)xk​=a2k×d≡−1 (mod n).

Như vậy giải thuật có thể triển khai thành các bước sau:

• Bước $1$: Phân tích n−1=2r×dn - 1 = 2^r \times dn−1=2r×d với $d$ là số tự nhiên lẻ và $r>0$.
• Bước $2$: Chọn ngẫu nhiên $a$ thuộc $[1,n-1]$ rồi đặt \text{mod_val} = a^d \text{ mod } n.
• Bước $3$: Liên tục bình phương \text{mod_val} và lấy số dư khi chia cho $n,$ nếu như gặp một số dư khác $1$ hoặc $n-1($ tương tự với $-1)$ thì trả về $\text{false}$.
• Bước $4$: Nếu như sau khi kiểm tra mọi xk mod nx_k \text{ mod } nxk​ mod n mà không tồn tại giá trị nào khác $1$ hoặc $n-1$ thì kết luận $\text{true}$.

Thực hiện giải thuật trên $k$ lần, với $k$ càng lớn ta sẽ có độ chính xác càng cao. Đối với giải thuật Miller - Rabin thì chỉ cần sử dụng $k=10$ là đã đủ an toàn.

Cài đặt:

int indian_multiplication(int a, int b, int mod) { if (b == 0) return 0; int half = indian_multiplication(a, b / 2LL, mod) % mod; if (b & 1) return (half + half + a) % mod; else return (half + half) % mod; } int modular_exponentiation(int a, int b, int mod) { if (b == 0) return 1LL; int half = modular_exponentiation(a, b / 2LL, mod) % mod; int product = indian_multiplication(half, half, mod); if (b & 1) return indian_multiplication(product, a, mod); else return product; } vector < int > eratosthenes_sieve(int max_value) { vector < bool > is_prime(max_value + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= max_value; ++i) if (is_prime[i]) for (int j = i * i; j <= max_value; j += i) is_prime[j] = false; vector < int > primes; for (int i = 2; i <= max_value; ++i) if (is_prime[i]) primes.push_back(i); return primes; } bool check_prime_by_miller_rabin(int n, int k) { if (n < 2) return false; if (n != 2 && n % 2 == 0) return false; int d = n - 1; while (d % 2 == 0) d /= 2; for (int i = 1; i <= k; ++i) { int a = rand() % (n - 1) + 1; int temp = d; int mod_val = modular_exponentiation(a, temp, n); while (temp != n - 1 && mod_val != 1 && mod_val != n - 1) { mod_val = indian_multiplication(mod_val, mod_val, n); temp *= 2; } if (mod_val != n - 1 && temp % 2 == 0) return false; } return true; }

Giải thuật có độ phức tạp $O(k\times \log (n))$.

3. Đếm số ước của một số trong O(n13)O(n^{\frac{1}{3}})O(n31​)

Ý tưởng: Nói dài dòng như vậy, nhưng bây giờ chúng ta mới đi vào ý chính của bài viết. Trước tiên, ta sẽ viết $n$ dưới dạng tích của hai số $x,y$ sao cho:

• Phân tích nguyên tố của $x$ chỉ gồm các số nguyên tố không vượt quá n13n^{\frac{1}{3}}n31​.
• Phân tích nguyên tố của $y$ chỉ gồm các số nguyên tố lớn hơn n13n^{\frac{1}{3}}n31​.

Dễ dàng nhận thấy, $x$ và $y$ là hai số nguyên tố cùng nhau, do chúng không có chung bất kỳ thừa số nguyên tố nào cả. Việc tìm ra $x$ có thể thực hiện rất dễ, bằng cách duyệt qua tất cả các số nguyên dương trong đoạn [2,n13][2, n^{\frac{1}{3}}][2,n31​] và thử chia $n$ cho những số đó tới khi không thể chia hết được nữa (giống với cách phân tích thừa số nguyên tố trong O(n)O(\sqrt{n})O(n​)). Ở bước này ta sẽ áp dụng thêm sàng lọc số nguyên tố để tìm nhanh ra các số nguyên tố không vượt quá n13n^{\frac{1}{3}}n31​.

Đến đây, bạn đọc có thể thắc mắc rằng, tại sao lại cần viết $n$ ở dạng $x\times y?$ Cần biết rằng, hàm $F(n)$ đếm số lượng ước nguyên dương của $n$ là một Hàm nhân tính, tức là $F(n)=F(x)\times F(y)$ nếu như $x$ và $y$ là hai số nguyên tố cùng nhau. Do đó, việc tính $F(n)$ sẽ được đưa về việc tính $F(x)$ và $F(y)$. Cụ thể ta tính $F(x)$ và $F(y)$ như sau:

• Đối với $F(x)$: Sử dụng sàng lọc số nguyên tố Eratosthenes để sinh ra tất cả các số nguyên tố không vượt quá n13n^{\frac{1}{3}}n31​. Sau đó, duyệt qua từng số nguyên tố và áp dụng Legendre's Formula để tính số mũ của từng thừa số nguyên tố đó trong $x,$ từ đó tính được $F(x)$.
• Đối với $F(y)$: Giả sử $y$ có thể được phân tích thành tích của ba số nguyên tố khác nhau, tức là y=p1×p2×p3y = p_1 \times p_2 \times p_3y=p1​×p2​×p3​. Vì $y$ chỉ bao gồm các thừa số nguyên tố lớn hơn n13,n^{\frac{1}{3}},n31​, nên p1×p2×p3>n,p_1 \times p_2 \times p_3 > n,p1​×p2​×p3​>n, điều này vô lí. Do đó điều giả sử không thể xảy ra và $y$ chỉ có thể chứa tối đa $2$ thừa số nguyên tố. Như vậy, ta nhận xét được rằng, sau khi chia $n$ cho $x,$ số $y$ chỉ có thể rơi vào một trong ba trường hợp:
  • TH1: $y$ là một số nguyên tố. Khi đó $F(y)=2$.
  • TH2: $y$ là bình phương của một số nguyên tố. Khi đó $F(y)=3$.
  • TH3: $y$ là tích của hai số nguyên tố khác nhau. Khi đó $F(y)=4$.

Việc kiểm tra $y$ thuộc vào trường hợp nào có thể được thực hiện bằng cách sử dụng giải thuật kiểm tra tính nguyên tố của Fermat hoặc Miller - Rabin như mình đã đề cập ở trên! Như vậy, chúng ta đã có thể cài đặt giải thuật đếm số ước của $n$ trong O(n13)O(n^{\frac{1}{3}})O(n31​)!

Cài đặt: Dưới đây là cài đặt C++ của giải thuật, đã được sử dụng để nộp thành công bài tập https://codeforces.com/gym/100753/attachments trên codeforces. Mình sẽ thực hiện bằng cả hai phương pháp kiểm tra số nguyên tố của Fermat và Miller - Rabin.

Code bằng giải thuật Fermat:

#include #define int long long #define task "Divisions_Fermat." using namespace std; vector < int > eratosthenes_sieve(int max_value) { vector < bool > is_prime(max_value + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= max_value; ++i) if (is_prime[i]) for (int j = i * i; j <= max_value; j += i) is_prime[j] = false; vector < int > primes; for (int i = 2; i <= max_value; ++i) if (is_prime[i]) primes.push_back(i); return primes; } void solution(int n) { vector < int > primes = eratosthenes_sieve(1000000); long long res = 1; for (int p: primes) { if (p * p * p > n) break; int cnt = 0; while (n % p == 0) { n /= p; ++cnt; } res *= (cnt + 1); } if (fermat_checking(n)) res *= 2LL; else { int squaroot = sqrt(n); if (squaroot * squaroot == n && fermat_checking(squaroot)) res *= 3; else if (n != 1) res *= 4; } cout << res; } main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; solution(n); return 0; }

Code bằng giải thuật Miller - Rabin:

#include #define int long long #define task "Divisions_Miller_Rabin." using namespace std; bool sqrt_is_integer(int n) { int squaroot = sqrt(n); return (squaroot * squaroot == n); } void solution(int n, int k) { vector < int > primes = eratosthenes_sieve(1000000); long long res = 1; for (int p: primes) { if (p * p * p > n) break; int cnt = 0; while (n % p == 0) { n /= p; ++cnt; } res *= (cnt + 1); } if (check_prime_by_miller_rabin(n, k)) res *= 2LL; else if (sqrt_is_integer(n) && check_prime_by_miller_rabin((int)sqrt(n), k)) res *= 3LL; else if (n != 1) res *= 4LL; cout << res; } main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; solution(n, 10); return 0; }

III. Tài liệu tham khảo