Trò chơi 3

Nguồn: CLUE OJ Độ khó: Trung bình Map / Set Phân tích thừa số nguyên tố

Đề bài

Trò chơi

Trong siêu thị GO có để một máy chơi Game để cho mọi người đến giải trí. Máy chơi Game này giao tiếp với mọi người thông qua bàn phím, màn hình và bộ nhớ của nó lưu trữ sẵn một số nguyên. Ban đầu số nguyên này khởi đầu bằng $1$. Máy chơi Game này hoạt động như sau:

• Một người chơi nhập một số nguyên từ bàn phím.
• Máy chơi Game sẽ nhân số trong bộ nhớ của nó với số nguyên vừa được nhập và kết quả được lưu lại chính bộ nhớ này.
• Máy sẽ hiển thị "YES" lên màn hình nếu như số trong bộ nhớ là một số chính phương. Khi đó người chơi sẽ là người may mắn nhận được một phần quà, ngược lại nếu số đó không phải số chính phương máy hiển thị chữ "NO" thì người đó không nhận được gì.

Yêu cầu: Đếm xem có bao nhiêu người chơi may mắn nhận được quà và xác định xem người chơi nào là người may mắn, người chơi nào không may mắn.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^6)$ là số lượng người tham gia chơi.
• Dòng tiếp theo là dãy số nguyên $a_1, a_2, \ldots, a_N$ với $(1 \le a_i \le 10^6)$ là các số nguyên do người chơi thứ $i$ nhập vào.

Kết quả:

• Dòng đầu tiên ghi số lượng người may mắn.
• Dòng thứ hai ghi kết quả tương ứng với $N$ người chơi. Nếu người chơi thứ $i$ mà may mắn thì ghi YES và ngược lại ghi NO. Mỗi từ cách nhau bởi một dấu cách.

Ràng buộc:

• Có 40% số điểm của bài với: $1 < n \le 18$, $1 \le a_i \le 9$.
• Có 30% số điểm của bài với: $1 \le a_i \le 9$.
• Có 30% số điểm còn lại không có ràng buộc gì thêm.

Giới hạn thời gian: 5 giây, bộ nhớ: 256 MB.

Ví dụ – input

4
2 3 6 36

Ví dụ – output

2
NO NO YES YES

Lời mở đầu

Số trong bộ nhớ sau người thứ $i$ chính là tích tiền tố $P_i = a_1 \cdot a_2 \cdots a_i$. Ở ví dụ: $P_1 = 2$, $P_2 = 6$ đều không chính phương; $P_3 = 36 = 6^2$ là chính phương nên người thứ 3 được quà; $P_4 = 36 \cdot 36 = 1296 = 36^2$ cũng chính phương. Vậy có 2 người may mắn: NO NO YES YES.

Cái khó là $P_i$ lớn khủng khiếp: $10^6$ số, mỗi số tới $10^6$ thì $P_N$ có tới 6 triệu chữ số! Không thể lưu $P_i$ mà phải nhìn số chính phương qua số mũ của các thừa số nguyên tố. Đây là một bài rất đẹp để dùng set.

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Ý tưởngsố mũ chẵn lẻCách 1nhân thẳngCách 22, 3, 5, 7Cách 3sàng + set

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

Bộ test có 100 test:

Test	N	$a_i$ lớn nhất	Tỉ lệ $a_i$ là số chính phương	Tỉ lệ YES
1–40	2 … 18	36	37%	17,9%
41–50	10.000	9	33%	6,3%
51–60	50.000	9	33%	6,2%
61–70	100.000	9	33%	6,3%
71–80	500.000	999.990	53%	13,5%
81–100	1.000.000	999.998	53%	12,4%

• Các test 71–100 có khoảng một nửa số $a_i$ là số chính phương (nhân vào không làm đổi tính chính phương), nhờ vậy câu trả lời YES xuất hiện khá nhiều. Nhưng có 20 test không có người nào may mắn – lúc đó dòng đầu là 0 và dòng hai toàn NO.
• Số $a_i = 1$ có xuất hiện (khoảng 2%), nhân với 1 thì $P$ giữ nguyên.

Subtask trong đề khớp với bộ test. Số test đúng của từng cách:

Subtask	Đề ghi	Test	Cách 1 (nhân thẳng)	Cách 2 (4 số nguyên tố)	Cách 3 (sàng + set)
1 (40%)	$1 < n \le 18$, $a_i \le 9$	1–40	40/40	40/40	40/40
2 (30%)	$a_i \le 9$	41–70	0/30	30/30	30/30
3 (30%)	không thêm	71–100	0/30	0/30	30/30

Ý tưởngChính phương ⇔ mọi số mũ đều chẵn

Phân tích $P = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$. Ta có:

Tính chất

$P$ là số chính phương $\iff$ mọi số mũ $e_1, e_2, \ldots, e_k$ đều chẵn. (Khi đó $P = \left(p_1^{e_1/2} \cdots p_k^{e_k/2}\right)^2$.)

Ta chỉ quan tâm số mũ chẵn hay lẻ. Vậy giữ một set $S$ gồm các số nguyên tố đang có số mũ lẻ trong $P$:

• Nhân $P$ với $a_i$: phân tích $a_i$ ra thừa số nguyên tố; mỗi lần gặp thừa số $p$ thì số mũ của $p$ tăng 1, tức là đổi chẵn ↔ lẻ: nếu $p$ đang có trong $S$ thì xoá, chưa có thì thêm.
• $P_i$ là số chính phương $\iff$ $S$ rỗng.

Để phân tích nhanh $10^6$ số, ta sàng trước mảng spf[x] = ước nguyên tố nhỏ nhất của $x$; khi đó phân tích $x$ chỉ cần chia liên tục cho spf[x], mỗi số mất không quá 20 bước (vì $2^{20} > 10^6$).

Em nhập các số người chơi nhập vào rồi bấm Tiếp để xem set các số nguyên tố mũ lẻ thay đổi thế nào:

Các số:

Ví dụ nhanh:

Cách 1Nhân thẳng rồi kiểm tra căn – Subtask 1

Với subtask 1: $n \le 18$ và $a_i \le 9$ nên $P \le 9^{18} \approx 1{,}5 \cdot 10^{17}$, vừa trong long long (tối đa khoảng $9{,}2 \cdot 10^{18}$). Ta cứ nhân thẳng rồi kiểm tra $P$ có phải số chính phương: lấy $r = \lfloor\sqrt{P}\rfloor$ và xem $r \cdot r = P$ không.

C++▶ Chạy tay từng dòng codeCách 1: nhân thẳng vào P (long long) rồi kiểm tra căn bậc hai.

Dữ liệu vào (stdin) – sửa thoải mái4 2 3 6 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Test của đề có số 36 > 9 nên mình dùng các bộ dữ liệu khác, đúng subtask 1 (mọi số ≤ 9).

1. sqrtl tính căn bằng số thực nên có thể lệch 1 đơn vị với số lớn. Hai vòng while chỉnh lại $r$ cho đúng là $\lfloor\sqrt{P}\rfloor$ – đây là thói quen tốt mỗi khi dùng sqrt với số nguyên lớn.
2. Dòng if(x < 0) return false; chỉ để chương trình không bị treo khi $P$ tràn số (ở các subtask sau) – kết quả khi đó đương nhiên là sai.
3. Bản Python dùng math.isqrt (căn nguyên chính xác) và số nguyên lớn nên không bao giờ tràn, nhưng $P$ dài hàng chục nghìn chữ số thì phép nhân và lấy căn rất chậm.

Không gian$O(n)$

Thời gian$O(n)$ (chỉ đúng khi $P$ không tràn số)

Kết quả chạy thật: Bản C++ đúng 40/100 test, sai ở test 41–100; test đúng chạy lâu nhất 0.00s. Bản Python đúng 50/70 test (mình chỉ chạy test 1–70), quá thời gian ở test 51–70; test đúng chạy lâu nhất 1.08s. Ăn trọn subtask 1 (40% điểm); bản C++ tràn số nên sai các test sau.

Cách 2Chỉ có 4 số nguyên tố 2, 3, 5, 7 – Subtask 1, 2

Khi $a_i \le 9$, mọi thừa số nguyên tố của $a_i$ chỉ có thể là $2, 3, 5, 7$. Vậy thay vì lưu $P$, ta chỉ cần nhớ 4 bit: số mũ của 2, 3, 5, 7 trong $P$ đang lẻ hay chẵn. $P$ chính phương khi cả 4 bit đều bằng 0.

C++▶ Chạy tay từng dòng codeCách 2: chỉ theo dõi tính chẵn lẻ số mũ của 2, 3, 5, 7.

Dữ liệu vào (stdin) – sửa thoải mái4 2 3 6 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. le[k] ^= 1 đổi 0 ↔ 1: mỗi lần chia được cho $p_k$ là số mũ tăng 1, tính chẵn lẻ đảo lại.
2. Với $10^5$ số, mình gom kết quả vào một string rồi in một lần cho nhanh.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 70/100 test, sai ở test 71–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 70/100 test, sai ở test 71–100; test đúng chạy lâu nhất 0.14s. Ăn subtask 1, 2 (70% điểm). Ở subtask 3, $a_i$ có thể chứa thừa số như $11, 13, \ldots$ mà code này bỏ qua nên sai.

Cách 3Sàng ước nguyên tố nhỏ nhất + set – Full điểm

Tổng quát hoá cách 2: không chỉ 4 số nguyên tố mà là mọi số nguyên tố, nên thay mảng le[4] bằng set<int> chứa các số nguyên tố đang có số mũ lẻ.

C++▶ Chạy tay từng dòng codeCách 3: sàng spf, set các số nguyên tố có số mũ lẻ.

Dữ liệu vào (stdin) – sửa thoải mái4 2 3 6 36

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Sàng spf: với mỗi $i$ chưa có spf (tức $i$ nguyên tố), gán spf[j] = i cho các bội $j$ chưa được gán. Vì $i$ duyệt tăng dần nên giá trị gán đầu tiên chính là ước nguyên tố nhỏ nhất.
2. Vòng while(a > 1) lấy lần lượt từng thừa số nguyên tố (có lặp) của $a$. Ví dụ $a = 12$: lấy $2$, $2$, $3$ – số 2 bị "đảo" 2 lần nên không đổi, chỉ có 3 bị đảo.
3. le.empty() kiểm tra set rỗng trong $O(1)$.
4. Nếu muốn nhanh hơn nữa có thể thay set bằng mảng bool đánh dấu và một biến đếm số phần tử đang lẻ – ý tưởng y hệt.

Không gian$O(\max a)$

Thời gian$O(\max a \cdot \log\log \max a + n \cdot 20 \log n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.36s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 2.04s.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Nhân thẳng + kiểm tra căn	C++	40/100	0.00s	Tràn số → sai từ test 41
	Python	50/70	> 5s	Số nguyên lớn nên không sai, nhưng quá chậm: quá thời gian test 51–70 (chỉ chạy test 1–70)
2. Chẵn lẻ của 2, 3, 5, 7	C++	70/100	0.01s	Sai test 71–100 (có thừa số nguyên tố khác)
	Python	70/100	0.14s	Sai test 71–100
3. Sàng + set số mũ lẻ	C++	100/100	0.36s	Full điểm
	Python	100/100	2.04s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình, giới hạn 5 giây như đề. Bài học rút ra: khi cần biết một tích khổng lồ có phải số chính phương không, đừng tính tích – hãy theo dõi tính chẵn lẻ của số mũ từng thừa số nguyên tố.

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 😇