C++ 将数字分成两个可整除的部分

c++server side programmingprogramming

在这个问题中，我们得到了一个可以解释为数字的字符串。现在我们必须将该字符串分成两部分，使得第一部分可以被 A 整除，第二部分可以被 B 整除(给我们两个整数)。例如 −

输入:str = "123", a = 12, b = 3
输出:YES
12 3
"12" 可以被 a 整除，"3" 可以被 b 整除。

输入:str = "1200", a = 4, b = 3
输出:YES
12 00

输入:str = "125", a = 12, b = 3
输出:NO

现在在这个问题中，我们将进行一些预先计算，这将使我们的程序更快，然后它将能够在更高的约束下工作。

寻找解决方案的方法

在这种方法中，我们将在字符串中运行两个循环，第一个从开始到结束，第二个从结束到开始。现在，在每一个点，我们对第一个循环中用 an 形成的整数和第二个循环中用 b 形成的整数取模，然后我们就可以找到答案了。

示例

#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++) // 前循环用于计算带有 a 的整数的模
        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--){//结束循环用于计算带有 b 的整数的模
        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) // 我们可以跳过 mod_a 不为零的所有位置
            continue;
        if (mod_b[i+1] == 0){ // 现在，如果 mod_b 的下一个索引也为零，那么这就是我们的划分点
            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";; // 否则我们打印 NO
}
// 驱动程序代码
int main(){
    string str = &"123"; // 给定字符串
    int a = 12, b = 3;
    divisionOfString(str, a, b);
    return 0;
}

输出

YES
12 3

上述代码的解释

在这种方法中，我们现在计算每次除法形成的余数。我们的第一个数字应该可以被 a 整除，因此我们运行一个前向循环，并存储该数字与 a 的模数。对于 b，我们运行一个后向循环，并存储模数，因为我们知道，如果任何位置的 an 的模数为零，并且下一个索引的 b 的模数为零，那么这就是我们的答案，因此我们将其打印出来。