Số Nguyên Tố Và Các Vấn đề Liên Quan - Viblo

I. Số nguyên tố và Hợp số

1. Giới thiệu

Số nguyên tố là số nguyên dương lớn hơn 111 và chỉ có đúng hai ước là 111 và chính nó.

Hợp số, là các số nguyên dương lớn hơn 111 và có nhiều hơn hai ước.

Lấy ví dụ: 555 là một số nguyên tố, vì nó chỉ có đúng hai ước là 111 và 555. Ngược lại 101010 là một hợp số vì nó có bốn ước là 1,2,51, 2, 51,2,5 và 101010. Số nguyên tố và các vấn đề xoay quanh nó luôn là một chủ đề được yêu thích trong Toán học nói chung và lập trình thi đấu nói riêng.

2. Kiểm tra tính nguyên tố của một số

2.1. Giải thuật cơ sở

Ý tưởng ban đầu rất đơn giản: Ta duyệt qua tất cả các số nguyên từ 222 tới n−1,n - 1,n−1, nếu như có số nào là ước của NNN thì kết luận nnn không phải số nguyên tố. Giải thuật có độ phức tạp O(n)O(n)O(n).

bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i < n; ++i) if (N % i == 0) return false; return true; }

2.2. Cải tiến:

Xuất phát từ nhận xét sau: Giả sử số nguyên dương nnn có ước là d (0<d≤n),d \ (0 < d \le \sqrt{n}),d (0<d≤n​), khi đó nnn sẽ có thêm một ước là nd (n≤nd≤n)\frac{n}{d} \ \left(\sqrt{n} \le \frac{n}{d} \le n\right)dn​ (n​≤dn​≤n). Như vậy ta chỉ cần kiểm tra các số nguyên từ 222 tới n\sqrt{n}n​ xem nnn có chia hết cho số nào không, nếu không thì kết luận nnn là số nguyên tố. Giải thuật có độ phức tạp chỉ là O(n)O(\sqrt{n})O(n​).

bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; ++i) if (n % i == 0) return false; return true; } II. Sàng lọc số nguyên tố Eratosthenes

1. Giới thiệu

Sàng Eratosthenes là một giải thuật cổ xưa do nhà Toán học người Hy Lạp Eratosthenes phát minh ra để tìm các số nguyên tố nhỏ hơn 100100100. Tương truyền, khi tìm ra thuật toán, ông đã lấy lá cọ và ghi tất cả các số từ 222 cho đến 100100100 lên đó, sau đó chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

Với sự phát triển của máy tính, sàng Eratosthenes trở thành một công cụ rất hữu dụng để tìm ra các số nguyên tố trong một khoảng nhất định, với điều kiện bộ nhớ có thể lưu trữ được.

2. Cài đặt giải thuật

Nguyên lý hoạt động của sàng Eratosthenes như sau: Xét các số nguyên tố từ 222 tới n,\sqrt{n},n​, với mỗi số nguyên tố ta sẽ đánh dấu các bội của nó mà lớn hơn nó đều là hợp số. Sau khi duyệt xong, tất cả các số chưa được đánh dấu sẽ là số nguyên tố. Dưới đây cài đặt sàng lọc các số nguyên tố từ 111 tới nnn.

bool is_prime[n + 1]; void eratosthenes_sieve(int n) { // Mảng đánh dấu một số có phải số nguyên tố không. // Ban đầu giả sử mọi số đều là nguyên tố. for (int i = 0; i <= n; ++i) is_prime[i] = true; // 0 và 1 không phải số nguyên tố. is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= n; ++i) if (is_prime[i]) // Nếu i là số nguyên tố for (int j = i * i; j <= n; j += i) // Loại bỏ các bội của i lớn hơn i is_prime[j] = false; }

Bạn đọc có thể thắc mắc tại sao các bội của iii lại không bắt đầu từ 2.i2.i2.i. Lí do là vì, vòng lặp duyệt các số nguyên tố tăng dần, khi tới số nguyên tố iii thì các bội 2.i,3.i,...,(i−1).i2.i, 3.i,..., (i - 1).i2.i,3.i,...,(i−1).i đều đã bị loại đi trước đó bởi các số nguyên tố nhỏ hơn iii rồi. Cũng chính nhờ điều này nên vòng lặp bên ngoài chỉ cần duyệt từ 222 tới n\sqrt{n}n​, giúp giảm độ phức tạp của giải thuật đi nhiều.

Đánh giá độ phức tạp

Quan sát cài đặt, ta nhận thấy:

• Với i=2i = 2i=2, vòng lặp bên trong lặp n2\frac{n}{2}2n​ lần.
• Với i=3i = 3i=3, vòng lặp bên trong lặp n3\frac{n}{3}3n​ lần.
• Với i=5i = 5i=5, vòng lặp bên trong lặp n5\frac{n}{5}5n​ lần. .........

Tổng số lần lặp sẽ là n.(12+13+15+⋯ )n.\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+ \cdots\right)n.(21​+31​+51​+⋯), độ phức tạp sẽ tiến tới O(n.log⁡n)O\big(n. \log n\big)O(n.logn).

3. Sàng số nguyên tố trên đoạn

Ở một số trường hợp, người ta cần tìm các số nguyên tố trên đoạn [L,R][L, R][L,R] cho trước và RRR có thể lên tới 1012,10^{12},1012, với điều kiện có thể tạo được một mảng có độ dài (R−L+1)(R - L + 1)(R−L+1).

Ý tưởng giải thuật như sau: Sàng lọc trước một mảng gồm các số nguyên tố trong đoạn [2...R],\big[2...\sqrt{R}\big],[2...R​], sau đó duyệt qua các số nguyên tố này, loại bỏ các bội của chúng nằm trong đoạn [L,R][L, R][L,R]. Code dưới đây cải tiến một chút để bỏ bớt bước tạo mảng số nguyên tố trong đoạn [2...R],\big[2...\sqrt{R}\big],[2...R​], nhằm tiết kiệm thời gian chạy.

bool is_prime[R + 1]; void range_eratosthenes(int L, int R) { int range = R - L + 1; for (int i = 2; i <= range; ++i) is_prime[i] = true; // Duyệt các bội của i từ bội nhỏ nhất thuộc đoạn [L, R]. for (long long i = 2; i * i <= R; ++i) if (is_prime[i]) for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) is_prime[j - L] = false; if (L == 1) is_prime[0] = false; }

Như vậy với một số XXX trong đoạn [L,R],X[L, R], X[L,R],X là số nguyên tố khi và chỉ khi is_prime[X−L]=true\text{is\_prime}[X - L]=trueis_prime[X−L]=true. Thuật toán có độ phức tạp là O((R−L+1).log(R)+R)O\big((R - L + 1).log(R) + \sqrt{R}\big)O((R−L+1).log(R)+R​). Trên thực tế nó chạy khá nhanh.

III. Phân tích thừa số nguyên tố

Vấn đề phân tích thừa số nguyên tố cũng khá được quan tâm trong lập trình thi đấu, và nó còn có một số ứng dụng khác trong số học. Dưới đây chúng ta sẽ xem xét vài phương pháp phân tích thừa số nguyên tố thường dùng.

1. Giải thuật cơ sở

Ta xét mọi số nguyên tố bắt đầu từ 2,2,2, nếu nnn chia hết cho số nguyên tố ppp thì chia nnn cho ppp tới khi không thể chia hết nữa, rồi tăng ppp lên và lặp lại công việc tới khi n=1n=1n=1. Trên thực tế thừa số nguyên tố chính là thành phần cấu tạo nên một ước của n,n,n, do đó khi tách hết một thừa số nguyên tố xxx khỏi nnn thì nnn sẽ không thể chia hết cho các bội lớn hơn xxx nữa.

Cài đặt

vector < int > extract(int n) { int p = 2; vector < int > prime_factor; // Lưu thừa số nguyên tố vào vector. while (n > 1) { while (N % p == 0) { prime_factor.push_back(p); n /= p; } ++p; } return prime_factor; }

2. Cải tiến lần 1

Xuất phát từ nhận xét sau: Không thể xảy ra trường hợp mọi thừa số nguyên tố của nnn đều lớn hơn n,\sqrt{n},n​, do đó chúng ta chỉ cần xét các ước của nnn từ 222 tới n\sqrt{n}n​ và chia dần nnn cho các ước của nó tới khi nnn bằng 111. Nếu không thể tìm được ước nào từ 222 tới n\sqrt{n}n​ thì nnn phải là một số nguyên tố. Độ phức tạp giải thuật là O(n)O(\sqrt{n})O(n​).

Cài đặt

vector < int > extract(int n) { vector < int > prime_factor; for (int i = 2; i * i <= n; ++i) while (n % i == 0) { prime_factor.push_back(i); n /= i; } if (n > 1) prime_factor.push_back(i); return prime_factor; }

3. Phân tích thừa số nguyên tố bằng sàng Eratosthenes

Từ hai giải thuật trên ta thấy: Ở mỗi bước phân tích cần tìm ra ước nguyên tố nhỏ nhất của nnn rồi chia nnn cho ước đó. Ta sẽ thay đổi sàng Eratosthenes đi một chút để lấy được ngay ước nguyên tố nhỏ nhất của nnn trong O(1)O(1)O(1) ở mỗi bước phân tích, điều này sẽ giúp giảm thời gian chạy đi đáng kể.

Cài đặt

int smallest_divisor[max_value + 1]; bool is_prime[max_value + 1]; void eratosthenes_sieve(int max_value) { // Mảng lưu ước nguyên tố nhỏ nhất của các số trong đoạn [1, max_value]. fill(smallest_divisor + 1, smallest_divisor + max_value + 1, 0); fill(is_prime, 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]) // Nếu i là số nguyên tố for (int j = i * i; j <= max_value; j += i) { is_prime[j] = false; // Ước nguyên tố nhỏ nhất của j là i. if (smallest_divisor[j] == 0) smallest_divisor[j] = i; } // Xét riêng các trường hợp i là số nguyên tố, // ước nguyên tố nhỏ nhất là chính nó. for (int i = 2; i <= max_value; ++i) if (is_prime[i]) smallest_divisor[i] = i; } vector < int > extract(int n) { // Sàng số nguyên tố tới một giá trị max_value nào đó. eratosthenes_sieve(max_value); vector < int > prime_factor; while (n > 1) { int p = smallest_divisor[n]; prime_factor.push_back(p); n /= p; } return prime_factor; }

Mặc dù việc thực hiện sàng Eratosthenes vẫn mất O(n.log⁡n),O\big(n.\log n \big),O(n.logn), tuy nhiên thao tác phân tích một số ppp thành thừa số nguyên tố chỉ mất độ phức tạp O(log⁡p)O(\log p)O(logp). Điều này sẽ rất có lợi trong các bài toán phải phân tích thừa số nguyên tố nhiều lần.

4. Đếm số ước của một số nguyên

Giả sử ta phân tích được nnn thành các thừa số nguyên tố ở dạng:

n=p1k1×p2k2×...×pmkmn=p_1^{k_1}\times p_2^{k_2}\times ... \times p_m^{k_m} n=p1k1​​×p2k2​​×...×pmkm​​

Các ước số của nnn sẽ phải có dạng:

p1r1×p2r2×...×pmrmp_1^{r_1}\times p_2^{r_2}\times ...\times p_m^{r_m} p1r1​​×p2r2​​×...×pmrm​​

với 0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km0 \le r_1 \le k_1, 0 \le r_2 \le k_2,..., 0 \le r_m \le k_m0≤r1​≤k1​,0≤r2​≤k2​,...,0≤rm​≤km​.

Theo nguyên lý nhân, ta thấy: r1r_1r1​ có k1+1k_1 + 1k1​+1 cách chọn, r2r_2r2​ có k2+2k_2 + 2k2​+2 cách chọn,..., rmr_mrm​ có km+1k_m + 1km​+1 cách chọn. Như vậy số lượng ước của nnn sẽ được tính theo công thức:

Fn=(k1+1)×(k2+1)×...×(km+1)F_n=(k_1+1)\times (k_2+1) \times ... \times (k_m+1) Fn​=(k1​+1)×(k2​+1)×...×(km​+1)

Từ đây, ta có ý tưởng đếm số ước của một số nguyên dương nnn như sau:

• Phân tích nnn thành thừa số nguyên tố.
• Đặt một biến cnt_x\text{cnt\_x}cnt_x là số lần xuất hiện của thừa số nguyên tố xxx trong phân tích của nnn. Ta vừa phân tích nnn vừa cập nhật số lượng thừa số nguyên tố lên biến cnt_x\text{cnt\_x}cnt_x.

Cài đặt 1

Tính số lượng ước nguyên dương của số nnn bằng phân tích nguyên tố trong O(n)O(\sqrt{n})O(n​):

int count_divisors(int n) { int total_divisor = 1; // Chắc chắn n có ước là 1. for (int i = 2; i * i <= n; ++i) { int cnt = 0; // Đếm số lượng thừa số nguyên tố i trong phân tích của N. while (n % i == 0) { ++cnt; N /= i; } total_divisors *= (cnt + 1); } if (n > 1) total_divisors *= 2; return total_divisors; }

Trong trường hợp cần đếm ước của nhiều số (khoảng 10610^6106 số chẳng hạn), và mỗi số đều có giá trị nhỏ hơn hoặc bằng 107,10^7,107, thì giải thuật trên sẽ bị Time Limit Exceeded. Khi đó, ta có thể cải tiến thuật toán bằng cách áp dụng luôn việc phân tích thừa số nguyên tố sử dụng Sàng Eratosthenes, khi đó việc đếm ước của mỗi số sẽ chỉ còn độ phức tạp là O(log⁡n)O(\log n)O(logn).

Cài đặt 2

Trong cài đặt này, ta sẽ tái sử dụng lại code Sàng số nguyên tố Eratosthenes và mảng smallest_divisor\text{smallest\_divisor}smallest_divisor ở phần phân tích thừa số nguyên tố bằng Sàng Eratosthenes bên trên.

Tính số lượng ước nguyên dương của số nnn bằng phân tích nguyên tố trong O(log⁡n)O(\log n)O(logn):

int count_divisors(int n) { int total_divisors = 1; while (n > 1) { int d = smallest_divisor[n], power = 0; while (n % d == 0) { ++power; n /= d; } total_divisors *= (power + 1); } return total_divisors; }

5. Tính tổng các ước số nguyên dương của một số nguyên dương

Định lý

Nếu một số nguyên dương nnn khi phân tích ra thừa số nguyên tố có dạng:

n=p1k1×p2k2×...×pmkm (ki≠0;∀i:1≤i≤m)n=p_1^{k_1}\times p_2^{k_2}\times ... \times p_m^{k_m} \text{ } (k_i \ne 0; \forall i: 1 \le i \le m) n=p1k1​​×p2k2​​×...×pmkm​​ (ki​=0;∀i:1≤i≤m)

thì tổng các ước nguyên dương của nó được tính theo công thức:

σ(n)=∏i=1m(piki+1−1pi−1)\sigma(n) = \prod_{i = 1}^m \left(\frac{p_i^{k_i + 1} - 1}{p_i - 1}\right) σ(n)=i=1∏m​(pi​−1piki​+1​−1​)

Chứng minh: Các ước số của nnn sẽ phải có dạng:

p1r1×p2r2×...×pmrmp_1^{r_1}\times p_2^{r_2}\times ...\times p_m^{r_m} p1r1​​×p2r2​​×...×pmrm​​

với 0≤r1≤k1,0≤r2≤k2,...,0≤rm≤km0 \le r_1 \le k_1, 0 \le r_2 \le k_2,..., 0 \le r_m \le k_m0≤r1​≤k1​,0≤r2​≤k2​,...,0≤rm​≤km​.

→\rightarrow→ Tổng các ước của nnn là:

σ(N)=∑r1=0k1∑r2=0k2⋯∑rm=0km(p1r1×p2r2×⋯×pmrm)\sigma(N) = \sum_{r_1=0}^{k_1} \sum_{r_2=0}^{k_2} \cdots \sum_{r_m = 0}^{k_m} (p_1^{r_1} \times p_2^{r_2} \times \cdots \times p_m^{r_m}) σ(N)=r1​=0∑k1​​r2​=0∑k2​​⋯rm​=0∑km​​(p1r1​​×p2r2​​×⋯×pmrm​​)

=∑r1=0k1p1r1×∑r2=0k2p2r2×⋯×∑rm=0kmpmrm (1)= \sum_{r_1=0}^{k_1} p_1^{r_1} \times \sum_{r_2=0}^{k_2} p_2^{r_2} \times \cdots \times \sum_{r_m=0}^{k_m} p_m^{r_m} \ (1) =r1​=0∑k1​​p1r1​​×r2​=0∑k2​​p2r2​​×⋯×rm​=0∑km​​pmrm​​ (1)

Mà ta có công thức dãy cấp số nhân sau:

p0+p1+p2+⋯+pn=pn+1−1p−1 (2)p^0 + p^1 + p^2 + \cdots + p^n = \frac{p^{n + 1} - 1}{p - 1} \ (2) p0+p1+p2+⋯+pn=p−1pn+1−1​ (2)

Từ (1)(1)(1) và (2)(2)(2), ta có:

σ(n)=p1k1+1−1p1−1×p2k2+1−1p2−1×⋯×pmkm+1−1pm−1\sigma(n) = \frac{p_1^{k_1 + 1} - 1}{p_1 - 1} \times \frac{p_2^{k_2 + 1} - 1}{p_2 - 1} \times \cdots \times \frac{p_m^{k_m + 1} - 1}{p_m - 1} σ(n)=p1​−1p1k1​+1​−1​×p2​−1p2k2​+1​−1​×⋯×pm​−1pmkm​+1​−1​

Cài đặt 1

Để tránh tràn số, ở đây tôi đặt luôn tất cả các số mang kiểu dữ liệu long long. Tùy vào bài toán mà các bạn sẽ điều chỉnh lại cho phù hợp.

Tuy nhiên, giải thuật này có sử dụng tới kĩ thuật tính nhanh lũy thừa aba^bab trong O(log⁡b)O(\log b)O(logb) bằng giải thuật Bình phương và Nhân. Các bạn có thể đọc trước về giải thuật này tại đây.

Tính tổng các ước của một số nguyên dương nnn trong O(n×log⁡n)O(\sqrt{n} \times \log n)O(n​×logn):

long long exponentiation(long long A, long long B) { if (B == 0) return 1LL; long long half = exponentiation(A, B / 2LL); if (B & 1) return half * half * A; else return half * half; } long long get_sum_divisors(long long n) { if (n == 1) return 1; long long x = 1, y = 1; for (int i = 2; i * i <= n; ++i) { long long cnt = 0; // Đếm số lượng thừa số nguyên tố i trong phân tích của n. while (n % i == 0) { ++cnt; n /= i; } if (cnt != 0) { x *= (exponentiation(i, cnt + 1) - 1); y *= (i - 1); } } if (n > 1) x *= n * n - 1, y *= (n - 1); return x / y; }

Cũng tương tự như khi đếm ước, ta có thể sử dụng sàng Eratosthene để tính tổng các ước của một số nguyên dương n,n,n, phương pháp này sẽ rất hữu dụng trong các bài toán cần tính nhanh tổng các ước của nnn.

Cài đặt 2

Trong cài đặt này, ta sẽ tái sử dụng lại code Sàng số nguyên tố Eratosthenes và mảng smallest_divisor\text{smallest\_divisor}smallest_divisor ở phần phân tích thừa số nguyên tố bằng Sàng Eratosthenes bên trên.

Tuy nhiên, do dùng tới Sàng nguyên tố nên giải thuật này chỉ có thể phân tích các số có giá trị khoảng 10710^7107 trở xuống. Các bạn cần lựa chọn thuật toán cho phù hợp với ràng buộc đề bài.

Tính tổng các ước nguyên dương của một số nnn trong O(log⁡2n)O(\log^2 n)O(log2n):

long long exponentiation(long long A, long long B) { if (B == 0) return 1LL; long long half = exponentiation(A, B / 2LL); if (B & 1) return half * half * A; else return half * half; } long long get_sum_divisors(int n) { long long x = 1, y = 1; while (n > 1) { int d = smallest_divisor[n], power = 0; while (n % d == 0) { ++power; n /= d; } x *= (exponentiation(d, power + 1) - 1); y *= (d - 1); } return x / y; } IV. Bài tập minh họa

1. Số nguyên tố đặc biệt

Đề bài

Một số nguyên dương XXX được gọi là số nguyên tố đặc biệt khi và chỉ khi nó có đúng 333 ước nguyên dương phân biệt.

Yêu cầu: Cho trước số nguyên dương NNN. Hãy đếm số lượng số nguyên tố đặc biệt từ 111 tới N?N?N?

Input:

• Chứa duy nhất số nguyên dương NNN.

Ràng buộc:

• 1≤N≤1091 \le N \le 10^91≤N≤109.

Subtasks

• Subtask 111 (50%50\%50% số điểm): 1≤N≤1031 \le N \le 10^31≤N≤103.
• Subtask 222 (50%50\%50% số điểm): Không có ràng buộc gì thêm.

Output:

• In ra danh sách các số nguyên tố đặc biệt từ 111 tới N,N,N, mỗi số trên một dòng.

Sample Input:

5

Sample Output:

4

Ý tưởng

Subtask 1

Duyệt tất cả các số và đếm ước của chúng.

Độ phức tạp: O(n×n)O\big(n \times \sqrt{n}\big)O(n×n​).

Subtask 2

Nhận thấy, số có 333 ước nguyên dương phân biệt chắc chắn phải là bình phương của một số nguyên tố. Vậy ta sẽ đi tìm số lượng số xxx là số nguyên tố thỏa mãn: 1≤x≤n,1 \le x \le \sqrt{n},1≤x≤n​, khi đó x2x^2x2 chính là một số nguyên tố đặc biệt.

Độ phức tạp: O(n)O(\sqrt{n})O(n​).

Cài đặt

#include <bits/stdc++.h> using namespace std; bool is_prime(int N) { if (N < 2) return false; for (int i = 2; i * i <= N; ++i) if (N % i == 0) return false; return true; } void solution(int N) { for (int i = 1; i * i <= N; ++i) if (is_prime(i)) cout << i * i << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; solution(N); return 0; }

2. Tìm số mũ

Đề bài

Cho trước hai số nguyên NNN và PPP.

Yêu cầu: Xác định giá trị MMM nguyên dương lớn nhất để PMP^MPM là ước số của N!N!N!

Input:

• Một dòng duy nhất chứa hai số nguyên NNN và PPP.

Ràng buộc:

• 1≤N,P≤300001 \le N, P \le 300001≤N,P≤30000.

Output:

• Đưa ra số MMM tìm được. Dữ liệu đảm bảo luôn tồn tại giá trị MMM nguyên dương thỏa mãn yêu cầu.

Sample Input:

7 3

Sample Output:

2

Ý tưởng

Giả sử n!n!n! có phân tích nguyên tố là:

p1k1×p2k2×⋯×pxkxp_1^{k_1} \times p_2^{k_2} \times \cdots \times p_x^{k_x} p1k1​​×p2k2​​×⋯×pxkx​​

Thì các ước số của n!n!n! phải có dạng:

p1k1′×p2k2′×⋯×pxkx′)p_1^{k'_1} \times p_2^{k'_2} \times \cdots \times p_x^{k'_x)} p1k1′​​×p2k2′​​×⋯×pxkx′​)​

với k1′≤k1,k2′≤k2,…,kx′≤kxk'_1 \le k_1, k'_2 \le k_2, \dots, k'_x \le k_xk1′​≤k1​,k2′​≤k2​,…,kx′​≤kx​.

Suy ra để PmP^mPm là ước của n!n!n! thì PmP^mPm cũng phải có dạng như trên. Giả sử phân tích nguyên tố của PPP là:

q1r1×q2r2×⋯×qlrlq_1^{r_1} \times q_2^{r_2} \times \cdots \times q_l^{r_l} q1r1​​×q2r2​​×⋯×qlrl​​

Thì PmP^mPm có phân tích là:

q1r1.m×q2r2.m×⋯×qlrl.mq_1^{r_1.m} \times q_2^{r_2.m} \times \cdots \times q_l^{r_l.m} q1r1​.m​×q2r2​.m​×⋯×qlrl​.m​

Nếu trong phân tích của PmP^mPm tồn tại một số nguyên tố không xuất hiện trong phân tích của n!n!n! thì chắc chắn không tìm được giá trị mmm. Tuy nhiên đề bài nói rằng chắc chắn luôn luôn tìm được mmm. Do đó, phân tích nguyên tố của PmP^mPm sẽ chỉ bao gồm các thừa số nguyên tố trong phân tích của n!n!n!:

p1r1.m×p2r2.m×⋯×pxrx.mp_1^{r_1.m} \times p_2^{r_2.m} \times \cdots \times p_x^{r_x.m} p1r1​.m​×p2r2​.m​×⋯×pxrx​.m​

Vì PmP^mPm là ước của n!n!n! nên:

r1.m≤k1;r2.m≤k2;… ;rx.m≤kxr_1.m \le k_1; r_2.m \le k_2; \dots; r_x.m \le k_x r1​.m≤k1​;r2​.m≤k2​;…;rx​.m≤kx​

⇔m≤⌊k1r1⌋;m≤⌊k2r2⌋;⋯ ;m≤⌊kxrx⌋\Leftrightarrow m \le \left\lfloor{\frac{k_1}{r_1}}\right\rfloor; m \le \left\lfloor{\frac{k_2}{r_2}}\right\rfloor; \cdots; m \le \left\lfloor{\frac{k_x}{r_x}}\right\rfloor ⇔m≤⌊r1​k1​​⌋;m≤⌊r2​k2​​⌋;⋯;m≤⌊rx​kx​​⌋

⇔m max=min(⌊kiri⌋);∀i:1≤i≤x\Leftrightarrow m \text{ max}= \text{min}\left(\left\lfloor{\frac{k_i}{r_i}}\right\rfloor\right); \forall i: 1 \le i \le x ⇔m max=min(⌊ri​ki​​⌋);∀i:1≤i≤x

Vì n,p≤30000n, p \le 30000n,p≤30000 nên chỉ cần áp dụng phân tích thừa số nguyên tố trong O(n)O(\sqrt{n})O(n​) là có thể vượt qua ràng buộc thời gian $1$s.

Cài đặt

#include <bits/stdc++.h> using namespace std; void extract(int n, vector < int > &power) { for (int i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; power[i]++; } } if (n > 1) power[n]++; } void solution(int n, int p) { vector < int > power1(n + 1); for (int i = 1; i <= n; i++) extract(i, power1); vector < int > power2(n + 1); extract(p, power2); int res = INT_MAX; for (int i = 2; i <= n; i++) if (power1[i] != 0 && power2[i] != 0) res = min(res, power1[i] / power2[i]); cout << res; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, p; cin >> n >> p; solution(n, p); return 0; }

3. Quà sinh nhật

Đề bài

Nguyên nhận được món quà sinh nhật thú vị. Đó là một dãy số nguyên dương. Anh ta quyết định biến đổi dãy số nhận được thành dãy toàn số 111.

Tại mỗi bước, anh ta chọn ra một tập hợp các số có cùng một ước số là số nguyên tố ppp nào đó, chia tất cả các số trong tập hợp này cho số ppp.

Yêu cầu: Hỏi rằng Nguyên phải thực hiện tối thiểu bao nhiêu bước biến đổi để thu được dãy toàn số 1?1?1?

Input:

• Dòng đầu tiên ghi số nguyên dương TTT là số bộ dữ liệu. Tiếp theo là TTT nhóm dòng, mỗi nhóm dòng mô tả một bộ dữ liệu theo qui cách sau:
  • Dòng đầu tiên ghi số nguyên dương NNN - số lượng số của dãy số.
  • Dòng thứ hai chứa NNN số nguyên a1,a2,…,aNa_1,a_2,\dots ,a_Na1​,a2​,…,aN​ phân tách nhau bởi dấu cách - dãy số được cho.

Ràng buộc:

• 1≤T≤51 \le T \le 51≤T≤5.
• 1≤N≤1051 \le N \le 10^51≤N≤105.
• 1≤ai≤106;∀i:1≤i≤N1 \le a_i \le 10^6; \forall i: 1 \le i \le N1≤ai​≤106;∀i:1≤i≤N.

Output:

• Với mỗi bộ dữ liệu in ra trên một dòng số nguyên - số lượng tối thiểu các bước cần thực hiện để thu được dãy chỉ chứa toàn số 111.

Sample Input:

1 3 1 2 4

Sample Output:

2

Ý tưởng

Mỗi lần ta chọn một số nguyên tố ppp và chia mọi số trong mảng AAA có chứa ppp cho nó, vì vậy ta có thể hiểu ý tưởng của bài là xét mọi thừa số nguyên tố xuất hiện trong phân tích nguyên tố của các ai,a_i,ai​, và lần lượt đếm số bước cần thực hiện để loại bỏ mỗi thừa số đó ra khỏi mọi số trong mảng AAA.

Ta sẽ phân tích ước nguyên tố ra với mỗi số aia_iai​ trong O(log⁡(ai))O\big(\log(a_i)\big)O(log(ai​)) sử dụng sàng số nguyên tố. Với mỗi thừa số nguyên tố p,p,p, giả sử nó xuất hiện trong kkk số của mảng AAA là ai1,ai2,…,aika_{i_1}, a_{i_2}, \dots, a_{i_k}ai1​​,ai2​​,…,aik​​ với số lần xuất hiện lần lượt là c1,c2,…,ck;c_1, c_2, \dots, c_k;c1​,c2​,…,ck​; thì tổng số lần chia cần thiết để loại bỏ ppp khỏi toàn bộ kkk số đó sẽ là max(c1,c2,…,ck)\text{max}(c_1, c_2, \dots, c_k)max(c1​,c2​,…,ck​) lần, bởi vì mỗi khi ta chia một số aia_iai​ cho ppp thì các số khác cũng chứa ppp cũng sẽ được gom nhóm cùng aia_iai​ để chia một lần.

Vậy dùng một mảng max_power[p]\text{max\_power}[p]max_power[p] để lưu số mũ cao nhất của thừa số nguyên tố ppp trong phân tích nguyên tố của tất cả các aia_iai​. Sau đó, lưu một mảng primes\text{primes}primes chứa mọi số nguyên tố khác nhau trong quá trình phân tích các aia_iai​. Kết quả cuối cùng sẽ là:

∑max_power[p];∀p∈primes\sum \text{max\_power}[p]; \forall p \in \text{primes} ∑max_power[p];∀p∈primes

Độ phức tạp: (T×n.log⁡(n))\big(T \times n.\log(n)\big)(T×n.log(n)).

Cài đặt

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5, max_value = 1e6; int a[maxn + 1], smallest_divisor[max_value + 1]; void 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; if (smallest_divisor[j] == 0) smallest_divisor[j] = i; } for (int i = 2; i <= max_value; ++i) if (is_prime[i]) smallest_divisor[i] = i; } void solution(int n, int a[]) { vector < int > max_power(max_value + 1, 0); vector < int > appear(max_value + 1, false); vector < int > primes; for (int i = 1; i <= n; ++i) { int x = a[i]; while (x > 1) { int p = smallest_divisor[x], power = 0; while (x % p == 0) { ++power; x /= p; } max_power[p] = max(max_power[p], power); if (!appear[p]) appear[p] = true, primes.push_back(p); } } int res = 0; for (int p: primes) res += max_power[p]; cout << res << endl; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); eratosthenes_sieve(max_value); int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; solution(n, a); } return 0; } V. Tài liệu tham khảo

• https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• https://vnoi.info/wiki/translate/he/Number-Theory-2.md
• https://cp-algorithms.com/algebra/factorization.html
• https://www.geeksforgeeks.org/segmented-sieve-print-primes-in-a-range/?ref=rp
• https://www.mathvn.com/2020/01/chung-minh-inh-li-ve-ham-tong-cac-uoc.html
• https://www.mathvn.com/2020/01/cong-thuc-tinh-tong-cac-uoc-nguyen.html

©️ Tác giả: Vũ Quế Lâm từ Viblo