CF 957E Novice's Mistake 题解
原题
K1o0n 的第一个编程问题是这样的”Noobish_Monk有 n 个朋友。 (1≤n≤100) 个朋友。每个朋友都给了他 a (1≤a≤10000) 个苹果。 (1≤a≤10000) 个苹果作为生日礼物。收到这样的礼物后，诺比什/蒙克很高兴，他回赠了 b (1≤b≤min(10000,a⋅n)) 个苹果。 (1≤b≤min(10000,a⋅n)) 个苹果给他的朋友们。诺比西和尚还剩下多少个苹果？”
K1o0n 写了一个解决方案，但不小心把 n 的值看成了字符串，所以 n⋅a−b 的值的计算方法不同。具体来说
当用字符串 n 乘以整数 a 时，他将得到字符串 s=n+n+⋯+n+n (a times) 从字符串 s 中减去整数 b 时，将删除最后的 b 个字符。如果 b 大于或等于字符串 s 的长度，则字符串 s将变为空。 了解到这一点后，ErnKor 开始关注在给定的 n 中，有多少对 (a,b) 满足问题的约束条件，而 K1o0n 的解给出了正确答案。
“解法给出了正确答案 “意味着它输出了一个非空字符串，这个字符串转换成整数后等于正确答案，即 n⋅a−b 的值。
输入
第一行包含一个整数 t ( 1≤t≤100) - 测试用例数。 对于每个测试用例，单行输入包含一个整数 n ( 1≤n≤100)。 保证在所有测试用例中， n 都是不同的。
输出
对于每个测试用例，按以下格式输出答案： 在第一行，输出整数 x - 给定 n 的坏测试次数。 在接下来的 x 行中，输出两个整数 ai 和 bi - K1o0n 在测试” n “中的解决方案的整数。 ai bi” 得到正确答案。
Input
32310Output
320 18219 2162218 22141165 16211262 2519题目大意：
给你一个整数n，现在对于n*a - b有两种运算：
- n作为一个字符往后延伸至a个，然后从最后减去b个字符
- n作为一个数字，进行运算n*a - b
需要你求出 (a, b) 不同的组合数，使得两种运算后的结果相同。
思考
此题的数据范围不大，使用暴力枚举再调整合适的枚举范围是可以通过的。
对于此题，我们容易想到O(n^2)的暴力解法，即从010000枚举a再从 0a*n 去枚举b
但是这样子做必定会超时，我们不可能直接按题目给的范围去直接枚举b
调整上界
由于在第一种操作中，减去b会使得na减去b个字符，结果的字符串字符数不可能为负数 因此b的上界即是na的字符串的最长长度，即 |n|*a，即 数字n变成字符串后的长度再乘每次枚举的a
所以我们确定b的上界为 |n|*a
int len = 0;while (tmp[len]) { arr[len] = tmp[len]-'0'; len++;}for (int a = 1; a <= 10000; a++) for (int b = 0; b <= a*len; b++)调整下界
回到题目观察数据范围，我们发现n*a - b的范围是严格小于 10^6的，也就是说，按照第一种操作，字符串的长度最多不会超过6个字符， 于是下界minB的计算：|n|∗a−minB≤6 minB=|n|∗a−6
比较两种计算的值
十进制逐位加，注意一个小技巧：这里对arr下标取余运算，我们设arr是一个大小为3的数组，下标存的是 n 的每一位数字
val = (n*a) - b; //具体值rep = (a*len - b); //目标的字符串有多长
if (!val || !rep) { break;}
int r = 0;for (int i = 0; i < rep; i++) { r = r * 10 + arr[i%len];}if (r == val) { ans.push_back({a, b});}题解代码
#include <bits/stdc++.h>using namespace std;
const int mod = 1e6+10;typedef long long ll;#define x first#define y secondtypedef pair<int, int> P;
void solve() { int n; cin >> n;
vector<P> ans; int val; int rep; int d;
int arr[3]; char tmp[256] {}; itoa(n, tmp, 10); int len = 0;
while (tmp[len]) { arr[len] = tmp[len]-'0'; len++; }
for (int a = 1; a <= 10000; a++) { //对于B: 上界: a*len-1，下界: a*len-6 (在区间内最多不会超过6个字符) for (int b = max(1, len*a -5); b <= a*len; b++) { val = (n*a) - b; //具体值 rep = (a*len - b); //目标的字符串有多长
if (!val || !rep) { break; }
int r = 0; for (int i = 0; i < rep; i++) { r = r * 10 + arr[i%len]; } if (r == val) { ans.push_back({a, b}); } } }
cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i].x << ' ' << ans[i].y << endl; }}
int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t; while (t--) solve();
return 0;}文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！