福尔认为,如果一个数x 中各位数之和为一个设定的值y ,则这个数是一个幸运数。福尔想知道的是,给定一个整数a ,不小于a 的最小幸运数是什么? 输入数据 输入数据有多组,每组为两个数串a,y(0≤a≤101000,0≤y≤105) ,分别为如上所述的两个整数。 输出数据 对每组输入数据,请在单独的行中数串满足条件的最小的幸运数,若不存在则输出-1。写c++代码
时间: 2024-02-12 11:02:33 浏览: 65
以下是一个可行的C++代码实现,使用了字符串类 `string` 和高精度运算类 `BigInt`:
```c++
#include <iostream>
#include <string>
using namespace std;
// 高精度整数类
class BigInt {
public:
BigInt() {}
BigInt(const string& s) : num(s) {}
BigInt operator+(const BigInt& b) const;
BigInt operator-(const BigInt& b) const;
BigInt operator*(int n) const;
bool operator<(const BigInt& b) const { return num < b.num; }
bool operator<=(const BigInt& b) const { return num <= b.num; }
bool operator>(const BigInt& b) const { return num > b.num; }
bool operator>=(const BigInt& b) const { return num >= b.num; }
bool operator==(const BigInt& b) const { return num == b.num; }
bool operator!=(const BigInt& b) const { return num != b.num; }
friend ostream& operator<<(ostream& out, const BigInt& x); // 输出流重载
string num;
};
// 重载加法运算
BigInt BigInt::operator+(const BigInt& b) const {
string a = num;
string c = b.num;
int n1 = a.size();
int n2 = c.size();
if (n1 < n2) {
for (int i = 0; i < n2 - n1; i++) {
a = "0" + a;
}
} else {
for (int i = 0; i < n1 - n2; i++) {
c = "0" + c;
}
}
int carry = 0;
string res = "";
for (int i = a.size() - 1; i >= 0; i--) {
int sum = a[i] - '0' + c[i] - '0' + carry;
res = to_string(sum % 10) + res;
carry = sum / 10;
}
if (carry) {
res = "1" + res;
}
return BigInt(res);
}
// 重载减法运算
BigInt BigInt::operator-(const BigInt& b) const {
string a = num;
string c = b.num;
int n1 = a.size();
int n2 = c.size();
if (n1 < n2) {
for (int i = 0; i < n2 - n1; i++) {
a = "0" + a;
}
} else {
for (int i = 0; i < n1 - n2; i++) {
c = "0" + c;
}
}
int borrow = 0;
string res = "";
for (int i = a.size() - 1; i >= 0; i--) {
int diff = a[i] - '0' - (c[i] - '0') - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
res = to_string(diff) + res;
}
while (res.size() > 1 && res[0] == '0') {
res.erase(0, 1);
}
return BigInt(res);
}
// 重载乘法运算
BigInt BigInt::operator*(int n) const {
int carry = 0;
string res = "";
for (int i = num.size() - 1; i >= 0; i--) {
int product = (num[i] - '0') * n + carry;
res = to_string(product % 10) + res;
carry = product / 10;
}
if (carry) {
res = to_string(carry) + res;
}
return BigInt(res);
}
// 重载输出流
ostream& operator<<(ostream& out, const BigInt& x) {
out << x.num;
return out;
}
// 求字符串数字的各位数字之和
int digitSum(const string& s) {
int sum = 0;
for (int i = 0; i < s.size(); i++) {
sum += s[i] - '0';
}
return sum;
}
int main() {
string a, y;
while (cin >> a >> y) {
BigInt A(a), Y(y);
BigInt ans = A; // 初始值为a
while (digitSum(ans.num) != Y.num[0] - '0') {
ans = ans + BigInt("1");
}
if (ans < A) {
cout << "-1" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```
该程序的核心部分是求最小幸运数的循环部分,每次将当前数加1,直到各位数字之和等于设定的值。如果最终结果小于原数a,则说明不存在符合条件的幸运数,输出-1。
阅读全文