Cho số tự nhiên N (0 <= N <= 10^1000) được biểu diễn dưới dạng nhị phân. Hãy kiểm tra xem N có phải là số chia hết cho 5 hay không? Đưa ra “Yes” nếu N chia hết cho 5, trái lại đưa ra “No”.
Do N rất lớn k thể làm cách thông thường.A/c cho em xin chút thuật toán tối ưu để giải quyết bài toán với ạ.Em cảm ơn ạ!!
Kiểm tra số nhị phân N có phải là số chia hết cho 5 hay không
1 Like
cho B là số biểu diễn dưới dạng nhị phân. B chia 5 dư r. Bây giờ ta thêm 1 chữ số nhị phân có giá trị x \in \{0,1\} vào bên phải số B, tạo được số B' mới có giá trị là B' = 2B + x. Vậy B' chia 5 có số dư bằng với 2B + x chia 5, hay đồng dư với (2r + x) \mod{5}.
ví dụ B = 8_{10} = 1000_2, B chia 5 dư r=3. Nếu thêm x=1 vào bên phải B sẽ tạo ra B' = 10001_2 = (8*2 + 1)_{10} = 17_{10}, B' chia 5 dư 2, cũng chính là số dư của 2r + x = 2*3 + 1 = 7 chia 5.
cho int r = 0; với từng chữ số nhị phân x của N từ bit cao tới bit thấp, ta tính r = (2*r + x) % 5; rồi xét giá trị cuối cùng của r, nếu bằng 0 thì N chia hết cho 5.
vd với N = 17_{10} = 10001_2:
- Ban đầu r = \textcolor{blue}0
- \textcolor{red}10001 \rightarrow r = (2 \times \textcolor{blue}0 + \textcolor{red}1) \mod 5 = \textcolor{blue}1
- 1\textcolor{red}0001 \rightarrow r = (2 \times \textcolor{blue}1 + \textcolor{red}0) \mod 5 = \textcolor{blue}2
- 10\textcolor{red}001 \rightarrow r = (2 \times \textcolor{blue}2 + \textcolor{red}0) \mod 5 = \textcolor{blue}4
- 100\textcolor{red}01 \rightarrow r = (2 \times \textcolor{blue}4 + \textcolor{red}0) \mod 5 = \textcolor{blue}3
- 1000\textcolor{red}1 \rightarrow r = (2 \times \textcolor{blue}3 + \textcolor{red}1) \mod 5 = \textcolor{blue}2
r cuối cùng có giá trị khác 0 nên N = 10001_2 ko chia hết cho 5 :V :V :V
11 Likes
Mình hy vọng là bạn giải xong bài này rồi: Chuyển số nhị phân sang số thập phân trong C++
Nếu xong rồi thì bạn chỉ cần kiểm tra chữ số cuối cùng có phải là 0 hoặc 5 là xong mà. 
5 Likes
5=101 chia hết cho 5 mà chế?
6 Likes
Xài mod thôi
Đổi nhị phân sang thập phân thì là
A_2 = a_na_{n-1}...a_0
A_{10} = a_n \times 2^n + a_{n-1} \times 2^{n - 1} + ... + a_0
Vậy số A_2 chia hết cho 5 khi A_{10} (đống cộng trừ kia) chia hết cho 5
Ta có:
(a + b) \mod c = (a \mod c + b \mod c) \mod c
Và
(a \times b) \mod c = (a \mod c \times b \mod c) \mod c
Vậy
a_n \times 2^n + a_{n-1} \times 2^{n - 1} + ... + a_0 \mod 5
\\ = (a_n \times 2^n \mod 5 + a_{n-1} \times 2^{n - 1} \mod 5 + ... + a_0 \mod 5) \mod 5
\\ = [((a_n \mod 5) \times (2^n \mod 5) \mod 5) + ((a_{n-1} \mod 5) \times (2^{n - 1} \mod 5) \mod 5) + ... + a_0 \mod 5] \mod 5
Do a_n chỉ có 2 giá trị {1, 0} nên khỏi cần tính a_n \mod 5 cũng được.
Làm sao tính 2^n \mod 5 nhanh?
Mình tính sơ nó có chu kỳ
1 2 4 3 lần lượt là 2^0, 2^1, 2^2, 2^3
->
- 2^n, n mod 4 = 0 -> 2^n mod 5 = 1
- 2^n, n mod 4 = 1 -> 2^n mod 5 = 2
- 2^n, n mod 4 = 2 -> 2^n mod 5 = 4
- 2^n, n mod 4 = 3 -> 2^n mod 5 = 3
-> Áp dụng mớ trên tính với 1 vòng lặp
return (Sigma (a_n * (2^n mod 5) mod 5)) mod 5 == 0
10 Likes
ờm cách này lẹ hơn, ko nghĩ ra 2^i chia 5 có chu kì 
5 Likes
Vì 2^4 \equiv1 \pmod 5 mà 
5 Likes
Cái này có định lý đó, cyclic group sinh bởi phần tử a, kí hiệu \langle a \rangle = \{ a^n | n \in \mathbb{N} \}, nếu order (cấp) của \langle a \rangle là hữu hạn, tức | \langle a \rangle |= m\in \mathbb{N}, thì \langle a \rangle đẳng cấu (đồng cấu + song ánh) với \mathbb{Z}/ \mathbb{mZ}.
8 Likes
Cảm thấy hoang mang giúp chủ thớt
8 Likes
thay vì chuyển sang nhị phân thì mình chuyển sang hệ cơ số 4 thì bài toán đã được giải quyết ạ
2 Likes
Lại tốn thêm một bước
3 Likes
Mình xin góp ý thôi: bài toán có N cách làm mà, cơ mà bạn nên tìm cách tối ưu nhất. Với bản thân thì có thể là cách tốt nhất mình biết rùi nhưng nên tham khảo các cách tốt hơn, tối ưu hơn tạo thói quen bạn ạ. Trước mình cũng chỉ làm cho chạy được, sau đó đụng data bự mới bắt đầu lọ mọ đi tối ưu hóa, cực kỳ tốn thời gian.
4 Likes
chủ thớt yêu cầu vậy nè bạn
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?