C++ Phân chia số thành hai phần chia hết

Cho chuỗi số, cắt thành 2 phần sao cho phần đầu chia hết cho A, phần sau chia hết cho B. Ví dụ:

Input: "123", a=12, b=3 → YES: 12 | 3
Input: "1200", a=4, b=3 → YES: 12 | 00
Input: "125", a=12, b=3 → NO

Phương pháp giải

Tiền tính modulo: duyệt từ trái sang phải tính mod_a[i] = số tạo bởi prefix[0..i] mod A. Duyệt từ phải sang trái tính mod_b[i] = số tạo bởi suffix[i..n-1] mod B. Tìm i sao cho mod_a[i]==0 và mod_b[i+1]==0.

Ví dụ minh họa

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

void divisionOfString(string &str, int a, int b) {
    int n = str.length();
    vector<int> mod_a(n+1, 0);
    mod_a[0] = (str[0]-'0') % a;
    for (int i=1; i<n; i++)
        mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;

    vector<int> mod_b(n+1, 0);
    mod_b[n-1] = (str[n-1]-'0') % b;
    int power10 = 10;
    for (int i=n-2; i>=0; i--) {
        mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10) % b;
        power10 = (power10 * 10) % b;
    }

    for (int i=0; i<n-1; i++) {
        if (mod_a[i] != 0) continue;
        if (mod_b[i+1] == 0) {
            cout << "YES\n";
            for (int k=0; k<=i; k++) cout << str[k];
            cout << " ";
            for (int k=i+1; k<n; k++) cout << str[k];
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    string str = "123";
    int a = 12, b = 3;
    divisionOfString(str, a, b);
    return 0;
}

Kết quả

YES 12 3

Giải thích

Tiền tính modulo prefix cho A và suffix cho B. Tìm điểm cắt thỏa cả hai điều kiện modulo = 0. Độ phức tạp O(n).

Kết luận

Đã giải bài toán cắt chuỗi số thành 2 phần chia hết cho A, B bằng tiền tính modulo. Code C++ áp dụng cho các ngôn ngữ khác. Hy vọng hữu ích.