Một cách xây dựng DFA kinh điển là nhận diện các số chia hết cho k. Trạng thái chính là số dư hiện tại. Cho k và một chuỗi bit w (đọc như số nhị phân, bit trái là bit cao nhất). Hãy cho biết giá trị của w có chia hết cho k hay không bằng cách mô phỏng: r ← (r*2 + bit) mod k.
Chuỗi rỗng biểu diễn giá trị 0 (chia hết cho mọi k).
Ví dụ:
Input:
3
110
Output:
YES
k.w gồm các ký tự 0/1 (dùng - cho chuỗi rỗng).1 ≤ k ≤ 10^6, |w| ≤ 10^5.
In YES nếu giá trị của w chia hết cho k, ngược lại in NO.
Ví dụ:
Đầu vào:
3
110
Đầu ra:
YES
Giải thích:
Đang tải editor...