Độ chẵn

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Thừa số 2

Đề bài

Cho một số nguyên dương $N$. Ta định nghĩa "độ chẵn" của số $N$ là số lượng thừa số chẵn tối đa trong cách phân tích số $N$ (thành tích các thừa số). Hãy tính "độ chẵn" của số $N$.

Ví dụ:

• $N = 36$ có "độ chẵn" là 2. Vì $36 = 6 \cdot 6$ $= 18 \cdot 2$ $= 2 \cdot 6 \cdot 3$ $= \dots$ Ta chỉ phân tích được 36 thành tích của tối đa 2 thừa số chẵn.
• $N = 109$ có "độ chẵn" là 0. Vì 109 là một số lẻ, không thể phân tích thành tích của bất kì thừa số chẵn nào.

Input: gồm một dòng duy nhất chứa một số nguyên dương $N$.

Output: gồm 1 số nguyên là "độ chẵn" của số $N$.

Giới hạn: $1 \le N \le 10^{18}$.

• 20% đầu tiên có $N \le 10^3$.
• 20% tiếp theo có $N \le 10^6$.
• 20% tiếp theo có $N \le 10^9$.
• 20% tiếp theo có $N \le 10^{12}$.
• 10% tiếp theo có $N \le 10^{15}$.
• 10% còn lại không có giới hạn gì thêm.

Ví dụ – input

100

Ví dụ – output

2

Giải thích: $100 = 2 \cdot 50 = 10 \cdot 10$: có 2 thừa số chẵn. Không thể có 3 thừa số chẵn vì khi đó tích phải chia hết cho $2^3 = 8$, mà 100 không chia hết cho 8.

Lời mở đầu

Đề bài nghe như phải thử mọi cách phân tích $N$ thành tích, nhưng chỉ cần một nhận xét nhỏ là bài toán thu gọn thành "$N$ chia hết cho 2 bao nhiêu lần" – một hàm đệ quy đúng 2 dòng. Mình sẽ đi từ cách đệ quy thử hết (đúng định nghĩa, ăn 40% điểm) tới cách gọn nhất.

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ưởngĐếm số 2Cách 1Thử hếtCách 2O(log N)

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

Bộ test có 100 test, mỗi test là một số $N$, chia đúng 6 nhóm như subtask của đề:

Test	N	Đáp án	Số test N lẻ
1 – 20	100 … 1 000	0 … 7	7
21 – 40	117 048 … 1 000 000	1 … 10	0
41 – 60	129 285 440 … 1 000 000 000	4 … 9	0
61 – 80	137 448 908 800 … 1 000 000 000 000	7 … 12	0
81 – 90	219 255 623 315 456 … 1 000 000 000 000 000	10 … 15	0
91 – 100	156 332 085 816 780 800 … 1 000 000 000 000 000 000	11 … 18	0

• Test 1 là ví dụ của đề ($N = 100$). Chỉ nhóm đầu có số lẻ (đáp án 0), từ test 21 trở đi $N$ đều chẵn.
• Test cuối mỗi nhóm là $10^3, 10^6, \dots, 10^{18}$ – test 100 là $N = 10^{18} = 2^{18} \cdot 5^{18}$, đáp án 18. Phải dùng long long.

Subtask	Điều kiện	Test	Cách ăn được
1 (20%)	$N \le 10^3$	1 – 20	Cách 1, 2
2 (20%)	$N \le 10^6$	21 – 40	Cách 1, 2
3 (20%)	$N \le 10^9$	41 – 60	Cách 2
4 (20%)	$N \le 10^{12}$	61 – 80	Cách 2
5 (10%)	$N \le 10^{15}$	81 – 90	Cách 2
6 (10%)	$N \le 10^{18}$	91 – 100	Cách 2

Ý tưởngMỗi thừa số chẵn "ăn" ít nhất một số 2

Gọi $k$ là số lần $N$ chia hết cho 2, tức $N = 2^k \cdot m$ với $m$ lẻ. Ví dụ $100 = 2^2 \cdot 25$ nên $k = 2$.

• Không thể nhiều hơn $k$: mỗi thừa số chẵn chứa ít nhất một thừa số 2. Nếu có $t$ thừa số chẵn thì tích chia hết cho $2^t$, nên $t \le k$.
• Luôn đạt được $k$: viết $N = \underbrace{2 \cdot 2 \cdots 2}_{k - 1 \text{ số}} \cdot (2m)$ – đúng $k$ thừa số chẵn (khi $k \ge 1$).

Kết luận

Độ chẵn của $N$ = số lần $N$ chia hết cho 2. Viết bằng đệ quy: dem(n) = 0 nếu $n$ lẻ (điểm dừng), ngược lại dem(n) = 1 + dem(n / 2).

Mỗi lời gọi chia đôi $n$, nên với $N \le 10^{18} < 2^{60}$ thì có không quá 60 lời gọi lồng nhau. Em nhập $N$ rồi bấm Tiếp để xem các lời gọi đi xuống tới số lẻ rồi cộng dần kết quả đi lên:

N =

Ví dụ nhanh:

Cách 1Đệ quy thử mọi thừa số chẵn – đúng định nghĩa

Chưa nghĩ ra nhận xét trên thì ta làm đúng như định nghĩa: chọn thừa số chẵn đầu tiên $d$ (thử mọi số chẵn $d$ chia hết $n$), phần còn lại $n / d$ lại phân tích tiếp – đó chính là bài toán con cùng dạng, nên gọi đệ quy f(n / d). Lấy max của $1 + f(n/d)$ trên mọi $d$. Nếu không có $d$ nào thì $f(n) = 0$ (phần còn lại để nguyên làm một thừa số, lẻ hay chẵn đều không làm giảm kết quả).

C++▶ Chạy tay từng dòng codeCách 1: thử mọi thừa số chẵn đầu tiên d, đệ quy cho phần còn lại n / d.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để ý ngăn xếp: cùng một f(3), f(1)... bị gọi lại nhiều lần từ các nhánh khác nhau – đó là lý do cách này chậm.

1. Không cần điểm dừng riêng: khi $n$ lẻ thì không có $d$ chẵn nào chia hết $n$, vòng lặp chạy xong mà không gọi đệ quy, trả về best = 0.
2. Mỗi lời gọi tốn $n / 2$ vòng lặp, và cây đệ quy rẽ nhánh theo mọi ước chẵn. Với $N \le 10^6$ vẫn chạy kịp, nhưng $N = 10^9$ thì riêng vòng lặp ngoài cùng đã $5 \cdot 10^8$ lần.

Không gian$O(k)$ – độ sâu đệ quy

Thời gianrất lớn: mỗi lời gọi tốn $O(n)$ và rẽ nhánh theo mọi ước chẵn

Kết quả chạy thật: C++ đúng 40/100 test (test 1–40, chậm nhất 0.062 giây); test 41–100 bị quá thời gian. Python đúng 40/100 test (test 1–40, chậm nhất 0.946 giây); test 41–100 bị quá thời gian.

Cách 2Đệ quy đếm số thừa số 2 – O(log N)

C++▶ Chạy tay từng dòng codeCách 2: mỗi lời gọi tách một số 2, dừng khi gặp số lẻ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điểm dừng if(n % 2 != 0) return 0;: số lẻ không tách thêm được số 2 nào. Vì $N \ge 1$ nên chia đôi mãi kiểu gì cũng gặp số lẻ (ít nhất là 1), đệ quy luôn dừng.
2. Bước đệ quy return 1 + dem(n / 2);: tách một số 2 ra, đếm tiếp phần còn lại.
3. $N$ tới $10^{18}$ nên phải đọc bằng long long (tối đa khoảng $9{,}2 \cdot 10^{18}$).

Không gian$O(\log N)$ – độ sâu đệ quy

Thời gian$O(\log N)$, tối đa 60 lời gọi

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.005 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.026 giây.

Ghi chú của mình: cách 2 (C++) đúng 100/100 test, chậm nhất 0.005 giây; bản Python cũng đúng hết. Cách 1 đúng 40/100 test – vừa đủ 2 subtask đầu, đúng như dự đoán. Bài học: trước khi thử hết mọi khả năng, hãy dừng lại tìm xem đại lượng cần tính thực chất phụ thuộc vào cái gì (ở đây chỉ là số mũ của 2).

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 😇