Chia số thành hai phần chia hết cho các số cho trước trong C++

Giới thiệu

Cho một số lớn (dưới dạng chuỗi) và hai số nguyên a, b. Tìm cách cắt chuỗi thành hai phần liên tiếp sao cho: phần đầu chia hết cho a, phần sau chia hết cho b.

Ví dụ

Số: "125333", a = 5, b = 3

Cắt tại vị trí 3: "125" | "333"

• 125 % 5 = 0 ✓
• 333 % 3 = 0 ✓

Mã nguồn hoàn chỉnh

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

void checkDivisibilityOfPrefixAndSuffix(string num, int prefix_divisor, int suffix_divisor) {
    int N = num.length();
    bool prefix_ok = false, suffix_ok = false;
    int split_index = 0;
    long long prefix = 0;
    
    // Tìm vị trí cắt cho phần đầu (prefix)
    for (int i = 0; i < N - 1; i++) { // Cần để lại ít nhất 1 chữ số cho suffix
        prefix = prefix * 10 + (num[i] - '0');
        if (prefix % prefix_divisor == 0) {
            prefix_ok = true;
            split_index = i;
            break;
        }
    }
    
    if (!prefix_ok) {
        cout << "Not possible" << endl;
        return;
    }
    
    // Kiểm tra phần sau (suffix)
    long long suffix = 0;
    for (int i = split_index + 1; i < N; i++) {
        suffix = suffix * 10 + (num[i] - '0');
    }
    
    if (suffix % suffix_divisor == 0) {
        suffix_ok = true;
    }
    
    if (prefix_ok && suffix_ok) {
        cout << prefix << " " << suffix << endl;
    } else {
        cout << "Not possible" << endl;
    }
}

int main() {
    string number = "125333";
    int prefix_divisor = 5;
    int suffix_divisor = 3;
    checkDivisibilityOfPrefixAndSuffix(number, prefix_divisor, suffix_divisor);
    return 0;
}

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

125 333

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

• Thời gian: O(n) - duyệt chuỗi 1 lần
• Không gian: O(1)

Lưu ý quan trọng

• Sử dụng long long để tránh tràn số với chuỗi dài (tối đa 18-19 chữ số)
• Với chuỗi rất dài (> 18 chữ số), cần dùng chia lấy dư theo từng chữ số (modulo arithmetic)
• Code gốc có lỗi logic: biến index được tăng 2 lần trong vòng lặp

Phiên bản hỗ trợ số rất lớn (Big Integer)

bool checkLargeNumber(string num, int a, int b) {
    int n = num.length();
    vector<int> prefix_mod(n), suffix_mod(n);
    
    // Tính prefix_mod[i] = số tạo bởi num[0..i] mod a
    long long cur = 0;
    for (int i = 0; i < n; i++) {
        cur = (cur * 10 + (num[i] - '0')) % a;
        prefix_mod[i] = cur;
    }
    
    // Tính suffix_mod[i] = số tạo bởi num[i..n-1] mod b
    cur = 0;
    long long power = 1;
    for (int i = n - 1; i >= 0; i--) {
        cur = ((num[i] - '0') * power + cur) % b;
        suffix_mod[i] = cur;
        power = (power * 10) % b;
    }
    
    // Tìm vị trí cắt
    for (int i = 0; i < n - 1; i++) {
        if (prefix_mod[i] == 0 && suffix_mod[i + 1] == 0) {
            cout << num.substr(0, i + 1) << " " << num.substr(i + 1) << endl;
            return true;
        }
    }
    return false;
}

Kết luận

Bài toán áp dụng modulo arithmetic để xử lý số lớn. Phiên bản tối ưu dùng mảng prefix/suffix modulo cho phép xử lý chuỗi dài bất kỳ.