Kiểm tra số lớn chia hết cho 37 trong C++

Giới thiệu

Kiểm tra số lớn (được biểu diễn dưới dạng chuỗi) có chia hết cho 37 hay không. Sử dụng quy tắc chia hết cho 37: chia số thành các nhóm 3 chữ số từ phải sang trái, cộng các nhóm lại, nếu tổng chia hết cho 37 thì số gốc cũng chia hết cho 37.

Quy tắc chia hết cho 37

Vì 1000 ≡ 1 (mod 37), nên:

Số N = aₖ×1000ᵏ + aₖ₋₁×1000ᵏ⁻¹ + ... + a₁×1000 + a₀

N ≡ aₖ + aₖ₋₁ + ... + a₁ + a₀ (mod 37)

Ví dụ: 4048675309

Nhóm 3 chữ số từ phải: 4 | 048 | 675 | 309
Tổng = 4 + 48 + 675 + 309 = 1036
1036 ÷ 37 = 28 → Chia hết ✓

Mã nguồn hoàn chỉnh

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

bool isNumberDivisibleBy37(string number, int n) {
    if (number == "0") return false;
    
    // Thêm số 0 ở đầu để độ dài chia hết cho 3
    if (n % 3 == 1) {
        number = "00" + number;
        n += 2;
    } else if (n % 3 == 2) {
        number = "0" + number;
        n += 1;
    }
    
    int groups_sum = 0;
    while (n != 0) {
        string group = number.substr(n - 3, 3);
        int group_value = (group[0] - '0') * 100 + 
                          (group[1] - '0') * 10 + 
                          (group[2] - '0') * 1;
        groups_sum += group_value;
        n -= 3;
    }
    
    // Nếu tổng >= 1000, đệ quy kiểm tra tiếp
    if (groups_sum >= 1000) {
        string new_number = to_string(groups_sum);
        return isNumberDivisibleBy37(new_number, new_number.length());
    } else {
        return groups_sum % 37 == 0;
    }
}

int main() {
    string number = "4048675309";
    if (isNumberDivisibleBy37(number, number.length())) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Kết quả chạy chương trình

Yes

Phân tích độ phức tạp

• Thời gian: O(log n) - mỗi lần đệ quy giảm độ dài số xuống ~3 lần
• Không gian: O(log n) - stack đệ quy

So sánh với các quy tắc chia hết khác

Kết luận

Quy tắc chia hết cho 37 dựa trên tính chất modulo của 1000. Kỹ thuật nhóm 3 chữ số áp dụng tương tự cho 7, 13 (vì 1001 = 7×11×13).