Phép chia dựa trên DFA (DFA based Division) trong C++

Sử dụng **DFA (Deterministic Finite Automaton)** để kiểm tra tính chia hết của một số nguyên num cho k bằng cách xử lý biểu diễn **nhị phân (bit)** của num. Ưu điểm: Tìm được cả **phần dư (remainder)**.

Ý tưởng cốt lõi

Xây dựng bảng chuyển trạng thái transTable[state][bit] với k trạng thái (0 đến k-1). Trạng thái đại diện cho phần dư hiện tại khi đọc các bit từ MSB -> LSB.

• Trạng thái hiện tại = rem.
• Đọc bit tiếp theo b (0 hoặc 1).
• Giá trị mới = (rem * 2 + b) % k.
• Đây chính là chuyển trạng thái: transTable[rem][b] = (rem * 2 + b) % k.

Xây dựng bảng chuyển trạng thái

For state = 0 to k-1:
  transTable[state][0] = (state * 2) % k;
  transTable[state][1] = (state * 2 + 1) % k;

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

void buildTransitionTable(int k, vector<array<int, 2>> &transTable) {
    transTable.resize(k);
    for (int state = 0; state < k; state++) {
        transTable[state][0] = (state * 2) % k;
        transTable[state][1] = (state * 2 + 1) % k;
    }
}

int dfaDivision(int num, int k) {
    if (k == 0) return -1; // Lỗi chia cho 0
    vector<array<int, 2>> transTable;
    buildTransitionTable(k, transTable);
    
    int state = 0;
    // Xử lý bit từ MSB (bit cao nhất) xuống LSB
    // Tìm bit cao nhất khác 0
    if (num == 0) return 0;
    
    int msbPos = 31 - __builtin_clz(num); // GCC/Clang builtin
    // Hoặc vòng lặp thủ công:
    // for (int i = 31; i >= 0; i--) if (num & (1<= 0; i--) {
        int bit = (num >> i) & 1;
        state = transTable[state][bit];
    }
    return state; // Phần dư
}

int main() {
    int num = 67, k = 5;
    int rem = dfaDivision(num, k);
    
    if (rem == 0)
        cout << num << " chia het cho " << k;
    else
        cout << num << " KHONG chia het cho " << k << ", phan du = " << rem;
    return 0;
}

Đầu ra

67 KHONG chia het cho 5, phan du = 2

Lưu ý: Code dùng `__builtin_clz` (GCC/Clang) để tìm MSB nhanh. Trên MSVC dùng `_BitScanReverse`. Cách này hiệu quả khi kiểm tra chia hết cho hằng số k nhiều lần (bảng chỉ xây 1 lần).