Độ chẵn
Đề 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.
1002Giả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ày chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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$).
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:
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ả).
- 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. - 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.
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)
- Đ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. - Bước đệ quy
return 1 + dem(n / 2);: tách một số 2 ra, đếm tiếp phần còn lại. - $N$ tới $10^{18}$ nên phải đọc bằng
long long(tối đa khoảng $9{,}2 \cdot 10^{18}$).
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.
Nhận xét
Đăng nhận xét