B. Good times Good times（Codeforces 2241）

B. Good times Good times 题解

题意简述

一个整数被称为good，当且仅当它的十进制表示中最多只含两种不同数字。

给定一个已经保证为 good 的整数x，要求构造一个整数y，满足：

• 2 <= y <= 10^9
• y是 good
• x * 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)