Số nguyên tố lớn nhất chia hết

Nguồn: CLUE OJ – Chương 46, Chương 47 Độ khó: Trung bình UCLN cả dãy Phân tích thừa số nguyên tố

Đề bài

Cho dãy số nguyên dương $a[1], a[2], a[3], \ldots, a[n]$. Tìm số nguyên tố lớn nhất mà tất cả mọi phần tử trong dãy đều chia hết được cho số nguyên tố đó.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên dương $n$ $(n \le 10^6)$;
• Dòng thứ hai là dãy $a[1], a[2], a[3], \ldots, a[n]$, mỗi số cách nhau bởi một khoảng trắng $(a[i] \le 10^{15})$.

Dữ liệu ra: một số nguyên duy nhất là số nguyên tố thỏa mãn. Nếu không tồn tại thì in ra $-1$.

Ràng buộc:

• $50\%$ số test đầu tiên có $n \le 10^3$ và $a[i] \le 10^7$;
• $50\%$ số test còn lại không có giới hạn gì thêm.

Thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ 1 – input

3
12 6 24

Ví dụ 1 – output

3

Ví dụ 2 – input

5
2 3 6 10 5

Ví dụ 2 – output

-1

Giải thích: ví dụ 1, các số nguyên tố chia hết cả $12, 6, 24$ là $2$ và $3$, lớn nhất là $3$. Ví dụ 2, không có số nguyên tố nào chia hết cả $2$ lẫn $3$ nên in $-1$.

Lời mở đầu

"Chia hết mọi phần tử" là dấu hiệu của ước chung, và mọi ước chung của dãy đều là ước của UCLN cả dãy. Thế là bài toán gồm 2 bước quen thuộc: gộp UCLN bằng Euclid, rồi tìm thừa số nguyên tố lớn nhất của một số. Mình đi từ cách thử từng số nguyên tố, tới cách UCLN + phân tích thừa số.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 2 mứcÝ tưởngUCLN cả dãyCách 1thử từng p ≤ minCách 2UCLN + phân tíchTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, chia 2 nhóm. Đặt $g$ là UCLN của cả dãy:

Test	n	a[i]	g	Đáp án
1–50	3 – 10.000	2 … 9.999.906	1 – 857	−1 – 857 (1 test in −1)
51–100	10.000 – 1.000.000	$10^{14}$ … $\approx 10^{15}$	151 – 999.999.999.999.989	151 – 999.999.999.999.989

• Lưu ý: ở nhóm 1 có test với $n$ tới $10\,000$ (đề ghi $n \le 10^3$), các cách dưới đây không bị ảnh hưởng.
• Ở 98/100 test, chính $g$ là số nguyên tố (nên đáp án là $g$). Test 100 khó nhất: $n = 10^6$, mọi phần tử đều bằng $999\,999\,999\,999\,989$ – một số nguyên tố cỡ $10^{15}$, muốn khẳng định nó nguyên tố phải thử chia tới $\sqrt{10^{15}} \approx 3{,}2 \cdot 10^7$.
• $a[i]$ tới $10^{15}$ nên phải dùng long long; đọc $10^6$ số nên nhớ ios::sync_with_stdio(0); cin.tie(0); (Python dùng sys.stdin.buffer.read()).

Subtask	Điều kiện	Các test	Cách ăn được
1 (50%)	$a[i] \le 10^7$	1 – 50	Cách 1, 2
2 (50%)	$a[i] \le 10^{15}$, $n \le 10^6$	51 – 100	Cách 2

Ý tưởngMọi ước chung đều là ước của UCLN

Một số $p$ chia hết mọi $a[i]$ khi và chỉ khi $p$ là ước chung của cả dãy, tức $p$ là ước của $g = \gcd(a[1], a[2], \ldots, a[n])$. UCLN cả dãy tính bằng cách "gộp dần": $g = \gcd(\gcd(\gcd(a[1], a[2]), a[3]), \ldots)$, bắt đầu từ $g = 0$ vì $\gcd(0, x) = x$.

Quy về

$$\text{Đáp án} = \text{thừa số nguyên tố lớn nhất của } g, \qquad g = \gcd(a[1], \ldots, a[n]); \quad g = 1 \Rightarrow -1$$

Thừa số nguyên tố lớn nhất của $g$ tìm bằng cách phân tích thừa số: thử chia $p = 2, 3, 4, \ldots$ khi $p \cdot p \le g$, chia hết thì chia mãi cho tới khi hết. Sau vòng lặp, nếu phần còn lại $> 1$ thì nó chính là thừa số nguyên tố lớn nhất (vì nó không có ước nào $\le$ căn của nó). Em nhập dãy rồi bấm Tiếp:

Dãy a:

Ví dụ nhanh:

Cách 1Thử từng p từ 2 tới số nhỏ nhất của dãy

Số nguyên tố cần tìm phải chia hết số nhỏ nhất của dãy nên không vượt quá $\min(a)$. Ta thử $p = 2, 3, \ldots, \min(a)$: kiểm tra mọi phần tử chia hết cho $p$ (dừng ngay khi gặp số không chia hết), nếu đúng thì kiểm tra $p$ nguyên tố. Vì $p$ tăng dần nên $p$ thỏa mãn cuối cùng là lớn nhất.

C++▶ Chạy tay từng dòng codeCách 1: thử p = 2..min(a); p chia hết cả dãy và là số nguyên tố thì cập nhật ans = p.

Dữ liệu vào (stdin) – sửa thoải mái3 12 6 24

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng ngoài chạy $\min(a)$ lần. Nhờ break ngay khi gặp phần tử không chia hết, phần lớn $p$ chỉ tốn 1 – 2 phép chia, nên với $a[i] \le 10^7$ vẫn rất nhanh.
• Với $a[i]$ cỡ $10^{14}$ – $10^{15}$ thì vòng ngoài không thể chạy hết.

Không gian$O(n)$

Thời gian$O(\min(a) \cdot n)$ trong trường hợp xấu

Kết quả chạy thật: bản C++ đúng 50/100 test (Subtask 1: 50/50, lâu nhất 0,065 giây; Subtask 2: 0/50). Bản Python chậm hơn nhiều, chỉ đúng 20/100 (test 1–20 có số nhỏ).

Cách 2UCLN cả dãy + phân tích thừa số nguyên tố – Full điểm

Đọc tới đâu gộp UCLN tới đó (không cần lưu mảng), rồi phân tích $g$ bằng cách thử chia tới $\sqrt{g}$. Nếu $g = 1$ thì vòng lặp không chạy và ans giữ nguyên $-1$.

C++▶ Chạy tay từng dòng codeCách 2: g = gcd của cả dãy (Euclid); phân tích g, thừa số nguyên tố cuối cùng là đáp án.

Dữ liệu vào (stdin) – sửa thoải mái3 12 6 24

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Gộp UCLN: $n$ lần gọi Euclid, mỗi lần $O(\log 10^{15})$ – rất nhanh. Phần tốn nhất thật ra là đọc $10^6$ số.
• Phân tích $g$: tối đa $\sqrt{g} \approx 3{,}2 \cdot 10^7$ lần thử – chỉ xảy ra khi $g$ là số nguyên tố lớn (test 100). C++ chạy khoảng 0,4 giây; Python thì không kịp ở test này.
• Có thể tăng tốc thêm bằng cách chỉ thử $p = 2$ rồi các số lẻ (giảm một nửa số lần thử), hoặc kiểm tra nhanh $g$ có nguyên tố không bằng thuật toán Miller–Rabin.

Không gian$O(1)$

Thời gian$O(n \log A + \sqrt{g})$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,407 giây (test 100). Bản Python đúng 99/100: các test khác đều dưới 0,6 giây, riêng test 100 bị quá thời gian vì vòng thử chia $3{,}2 \cdot 10^7$ lần.

Tổng kếtKết quả chạy thật trên bộ test

Mình chấm cả 2 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Subtask 1 test 1–50	Subtask 2 test 51–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	50/50	0/50	50/100	0,065s
Cách 1 – Python	20/50	0/50	20/100	0,025s
Cách 2 – C++	50/50	50/50	100/100	0,407s
Cách 2 – Python	50/50	49/50	99/100	0,596s

Ghi chú của mình: cả 2 cách đều cho đáp án đúng ở mọi test chạy kịp. Kỹ thuật cần nhớ: "số chia hết mọi phần tử của dãy" ⇔ "ước của UCLN cả dãy" – đưa bài toán trên cả dãy về bài toán trên một số $g$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇