本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。
题目简述
求满足以下条件的小于 \(10 ^ n\) 数最大是多少？
-
每一位数字均相同；
-
是 \(m\) 的倍数。
数据范围：\(1\le n\le 10^5\)，\(1\le m\le 10^9\)。
思路
首先每位数字都相同很好满足，仅需枚举 \(n\) 位后，枚举每位的数字 \(1 \sim 9\)，注意不包含 \(0\)，因为最高位不能为 \(0\)。
接着想要满足是 \(m\) 的倍数，可以想到类似动态转移的思路，定义二维数组 \(mp[i][j]\) 表示在有 \(i\) 位数的情况下每位都为 \(j\) 的数除以 \(M\) 的余数。在枚举中实时更新答案，因为位数是从 \(1 \sim N\)，每位是从 \(1 \sim 9\)，所以存储的答案一定为最大的解。
代码实现
经过以上分析及一些数组设计，很容易即可得到代码。首先我们先看一下 \(mp\) 数组的处理：
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= 9; j ++) {
mp[i][j] = (mp[i - 1][j] * 10 + j) % m;
if(!mp[i][j]) ans1 = i, ans2 = j;
}
可以看到第三行对于 \(mp\) 数组状态的转移：
\[mp_{i,j} \gets mp_{i-1,j}
\]
可以从 \(i-1\) 位都是 \(j\) 的余数转移过来，根据同余的相关知识很容易推出转移方程式：
\[mp_{i,j} \gets (mp_{i-1,j} \times 10 + j) \% M
\]
解决状态转移后需更新答案，这一部分很简单就不在赘述。接着需要在处理 \(mp\) 数组后，特判 \(-1\) 的情况：
if(!ans1 || !ans2) {
cout << "-1\n";
return 0;
}
这样整体代码框架就完成了。
AC code
#include<iostream>
using namespace std;
long long n, m, mp[100005][15];
long long ans1, ans2;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= 9; j ++) {
mp[i][j] = (mp[i - 1][j] * 10 + j) % m;
if(!mp[i][j]) ans1 = i, ans2 = j;
}
if(!ans1 || !ans2) {
cout << "-1\n";
return 0;
}
for(int i = 1; i <= ans1; i ++) cout << ans2;
return 0;
}
\[\text{The End!}
\]