90分求助
查看原帖
90分求助
1770342
rqliyanzhuo楼主2025/7/3 10:32
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string findMinNumber(int n, int p, int r) {
    int min_sum = 1; // 首位至少为1,其余位至少为0,总和最小为1
    int max_sum = 9 * n; // 每位最大为9,总和最大为9*n

    // 寻找满足 sum ≡ r mod p 的最小sum(不小于min_sum)
    int s = ((min_sum - r + p - 1) / p) * p + r;
    if (s < min_sum) {
        s += p;
    }
    if (s > max_sum) {
        return ""; // 不存在这样的sum
    }

    // 构造各位数字,使总和为s且数最小
    vector<int> digits(n, 0);
    int remaining = s;

    // 处理首位(第0位),至少为1
    digits[0] = max(1, remaining - 9 * (n - 1));
    remaining -= digits[0];

    // 处理中间位(从第1位到第n-2位)
    for (int i = 1; i < n - 1; ++i) {
        int max_possible = 9 * (n - 1 - i); // 剩余位最大能贡献的总和
        digits[i] = max(0, remaining - max_possible);
        remaining -= digits[i];
    }

    // 处理最后一位
    digits[n - 1] = remaining;

    // 转换为字符串
    string res;
    for (int d : digits) {
        res += (char)('0' + d);
    }
    return res;
}

int main() {
    int n, p;
    cin >> n >> p;

    // 从余数0开始寻找,找到第一个可能的结果
    for (int r = 0; r < p; ++r) {
        string ans = findMinNumber(n, p, r);
        if (!ans.empty()) {
            cout << ans << endl;
            return 0;
        }
    }

    return 0;
}
2025/7/3 10:32
加载中...