题目描述 给定一个长度可达$1000$位的非负整数字符串$s$,以及两个正整数$a$和$b$，要求将$s$从某个位置切割成两部分，使得：

1. 切割后得到的左半部分和右半部分均为正整数，且不含前导零；
2. 左半部分能够被$a$整除；
3. 右半部分能够被$b$整除。

如果存在多种切割方式，需返回使得左半部分数值最大的那一种；若无法切割则输出 NO。

思路

1. 记字符串长度为$n$，切割位置为$i$（$1 \le i \le n-1$），左半部分为$s[0..i-1]$，右半部分为$s[i..n-1]$。

2. 为了快速判断每个前缀/后缀是否可被整除，使用前缀余数和后缀余数：

   • 定义数组$text{pref}[i]$ 为字符串前$i$ 位（即$s[0..i-1]$）对$a$ 取模的结果；
   • 定义数组$text{suf}[i]$ 为字符串从第$i$位到末尾（即$s[i..n-1]$）对$b$取模的结果。

3. 前缀余数的递推： ${pref}[0]=0$,${pref}[i]$=(${pref}[i-1]$ * 10 + ($s[i-1]-'0'$))mod $a$$

4. 后缀余数的递推： 令权重$p=1$，初始${suf}[n]=0$，从右向左遍历$i=n-1..0$： $text{suf}[i]$=($(s[i]-'0'$) * $p$ + ${suf}[i+1]$)mod $b$,$p$=($p * 10$) mod $b$

5. 为了使左半部分最大，我们应当优先考虑更靠右的切割位置： 从$i=n-1$递减到$1$，若满足

   • ${pref}[i]==0$，
   • ${suf}[i]==0$，
   • 右半部分首位$s[i]\neq '0'$， 则找到最优切割，立即输出。

6. 若遍历完所有位置仍未找到，输出 NO。

该算法时间复杂度为$O(n)$，空间复杂度为$O(n)$，可轻松处理$n\le1000$ 的情况。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();

    int a, b;
    cin >> a >> b;

    vector<int> pref(n+1, 0), suf(n+1, 0);
    // 计算前缀余数：pref[i] = s[0..i-1] mod a
    for (int i = 1; i <= n; i++) {
        pref[i] = (pref[i-1] * 10 + (s[i-1] - '0')) % a;
    }

    // 计算后缀余数：suf[i] = s[i..n-1] mod b
    long long p = 1; // 当前位权
    for (int i = n-1; i >= 0; i--) {
        suf[i] = ((s[i] - '0') * p + suf[i+1]) % b;
        p = (p * 10) % b;
    }

    // 从右向左枚举切割点，优先保证左半部分最大
    for (int i = n-1; i >= 1; i--) {
        // 右半部分不能有前导零
        if (s[i] == '0') continue;
        if (pref[i] == 0 && suf[i] == 0) {
            cout << "YES\n";
            cout << s.substr(0, i) << "\n";
            cout << s.substr(i) << "\n";
            return 0;
        }
    }

    cout << "NO\n";
    return 0;
}

Python

# 读取输入
s = input().strip()
n = len(s)
a, b = map(int, input().split())

# 计算前缀余数 pref[i] = s[:i] mod a
pref = [0] * (n+1)
for i in range(1, n+1):
    pref[i] = (pref[i-1] * 10 + int(s[i-1])) % a

# 计算后缀余数 suf[i] = s[i:] mod b
suf = [0] * (n+1)
p = 1  # 当前位权
for i in range(n-1, -1, -1):
    suf[i] = (int(s[i]) * p + suf[i+1]) % b
    p = (p * 10) % b

# 从右向左枚举切割点
for i in range(n-1, 0, -1):
    if s[i] == '0':  # 后半部分有前导零，不允许
        continue
    if pref[i] == 0 and suf[i] == 0:
        print("YES")
        print(s[:i])
        print(s[i:])
        break
else:
    print("NO")

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = s.length();
        int a = in.nextInt();
        int b = in.nextInt();
        
        // 前缀余数
        int[] pref = new int[n+1];
        for (int i = 1; i <= n; i++) {
            pref[i] = (pref[i-1] * 10 + (s.charAt(i-1) - '0')) % a;
        }
        
        // 后缀余数
        int[] suf = new int[n+1];
        long p = 1;
        for (int i = n-1; i >= 0; i--) {
            suf[i] = (int)(((s.charAt(i) - '0') * p + suf[i+1]) % b);
            p = (p * 10) % b;
        }
        
        // 枚举切割点，优先保证左半部分最大
        for (int i = n-1; i >= 1; i--) {
            if (s.charAt(i) == '0') continue;  // 后半部分首位不为 '0'
            if (pref[i] == 0 && suf[i] == 0) {
                System.out.println("YES");
                System.out.println(s.substring(0, i));
                System.out.println(s.substring(i));
                return;
            }
        }
        
        System.out.println("NO");
    }
}

题目内容

请将一个长整数切割成两部分，并使得这两部分分别满足以下条件:

第一部分:能够被整数$a$整除。

第二部分:能够被整数$b$整除。

切割后得到的两部分分别为正整数，并且不能有前导零。

给定一个长整数字符串和两个整数$a$和$b$，你需要判断是否能够找到一种切割方式，使得满足上述条件。

如果可以切割，输出切割后的两部分。如果不可以切割，则输出$NO$。

备注:

1.如果存在多种切割方式，请返回使第一部分的数值最大的切割方式。

2.切割出的正整数不能包含前导$0$，如$0$，$01$，$0012$都是不允许的。

输入描述

第一行是一个大整数，这个整数的长度最大可达$1000$位

第二行包含两个整数$a$和$b$，其中$1≤a,b≤10^6$

输出描述

如果存在合适的切割方式，输出$YES$，然后输出两行分别为切割后的左部分和右部分。

如果不存在合适的切割方式,输出$NO$

样例1

输入

116401024
97 1024

输出

YES
11640
1024

说明

$11640$能被$97$整除

$1024$能被$1024$整除

样例2

输入

284254589153928171911281811000
1009 1000

输出

YES
2842545891539
28171911281811000

说明

$2842545891539$能被$1009$整除

$28171911281811000$能被$1000$整除

样例3

输入

120
12 1

输出

NO

说明

要求切割为两个正整数，$120$切割成$12$和$0$，第二部分$0$不是正整数，所以返回$NO$