B. Good times Good times 题解
题意简述
一个整数被称为good，当且仅当它的十进制表示中最多只含两种不同数字。
给定一个已经保证为 good 的整数x，要求构造一个整数y，满足：
2 <= y <= 10^9y是 goodx * y也是 good
如果有多个合法答案，输出任意一个即可。
核心构造
设x的十进制长度为n。
当n <= 8时，直接取：
y = 10^n + 1例如：
x = 299 n = 3 y = 1001 x * y = 299 * 1001 = 299299可以看到，乘积就是把x拼接了两次。
为什么这样一定正确？
因为：
x * (10^n + 1) = x * 10^n + x其中x * 10^n会把x左移n位，相当于在后面补n个0。
再加上x，结果就是：
xx也就是x自己拼接自己。
题目保证x是 good，也就是说x本身最多只含两种数字。把它复制一遍后，数字种类不会变多，所以x * y一定也是 good。
同时，当n <= 8时：
y = 10^n + 1 <= 100000001 <= 10^9并且y只包含数字1和0，所以y本身也是 good。
特殊情况
题目中有：
1 <= x <= 10^8因此x最多是9位数。
唯一的9位情况是：
x = 100000000此时不能再取10^9 + 1，因为会超过10^9。
我们直接取：
y = 10则：
x * y = 100000000 * 10 = 1000000000它只包含数字1和0，仍然是 good。
构造示意
x = 6767 n = 4 y = 10001 6767 * 10001 ------------- 6767 + 67670000 ------------- 67676767乘积67676767仍然只含数字6和7。
C++ 代码
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;while(t--){string x;cin>>x;intn=x.size();if(n==9){cout<<10<<'\n';}else{longlongy=1;for(inti=0;i<n;i++){y*=10;}cout<<y+1<<'\n';}}return0;}复杂度分析
每个测试用例只需要计算10^n，其中n <= 9。
- 时间复杂度：
O(t) - 空间复杂度：
O(1)