题解

思路

设 $R_i$ 表示由 $i$ 个数字 $1$ 组成的整数，那么任意候选答案都可以写成 $dR_i$，其中 $1\le d\le 9$、$1\le i\le N$。

做法

不必真的构造这个可能长达十万位的数，只需维护余数：若当前 $r=R_{i-1}\bmod M$，则 $R_i\bmod M=(10r+1)\bmod M$。对每个长度从 $9$ 到 $1$ 检查数位 $d$，第一个满足 $dr\equiv0\pmod M$ 的数位就是该长度下的最优选择。

按长度从小到大扫描，并用每个新发现的合法候选覆盖答案即可，因为位数更多的重复数字一定更大；位数相同时，数位越大越优。最后输出记录的数位和长度，若始终不存在合法候选则输出 $-1$。

复杂度

每个长度只检查九个数位，时间复杂度为 $O(N)$，除输出外额外空间为 $O(1)$。