根据题目可以知道：我们要求最小的 $k$ 的取值。

等式 $10^k=N \times P + Q$ 可以转换为：$10^k \equiv Q (mod\,\, P)$

讨论 $10$ 和 $P$ 互质的情况 ：

由欧拉定理可知：

$$10^t \equiv 10^{t\,\,mod \,\,\varphi (p)} \,\,(mod \,\, P) $$

又知 $\varphi (P) < P$ ， 那么考虑暴力枚举 $1 \sim P$ , 必然可以找出最小的非负整数 $t$

设 $k = \sqrt{P} + 1 \,, \, t = kx-y \,\, (x \in [1,k] \,\, , \, \, y \in [0,k-1])$

通过枚举 $x,y$ 一定可以遍历到 $1 \sim P$ (开始的时候要对 $x=0$ 进行判断)

发现 $x,y \sim \Theta (\sqrt{P})$ 显然时间复杂度是不被接受的。那么考虑优化:

将问题转换为：

$$10^{kx} \equiv Q \times 10^y (mod \,\, P)$$

用一个哈希表讲右边所有的取值与 $y$ 的对应存下来，然后枚举 $x$ ,在哈希表中查找是否有与 $a^{kx}$ 对应的 $y$ 即可。预处理和枚举的时间复杂度都是 $\Theta(\sqrt{P})$ 。

讨论此时不要求 $10$ 和 $P$ 互质：

有：

$$10^t \equiv Q(mod \,\, P) \Leftrightarrow 10^t + N\times P = Q $$

令 $d = \gcd(10,P)$ ，左等式显然能被 $d$ 整除，那么可以分为以下两种情况：

• $d\,\nmid Q$ 无解

• $d \, \mid Q$

  $$\frac{10}{d}10^{t-1} + N \times\frac{P}{d} = \frac{Q}{d}\\ \frac{10}{d}10^{t-1} \equiv \frac{Q}{d}\,\, (mod \,\, \frac{P}{d})\\ \frac{10}{d}10^{t-1} \equiv \frac{Q}{d} \times (\frac{10}{d})^{-1}\,\, (mod \,\, \frac{P}{d}) $$

如果 $10$ 和 $\frac{P}{d}$ 已经互质了，那么直接使用前面的方法即可，如果不互质，递归执行步骤。实际上，由于因数有限，递归次数必然不会超过 $O(log\,\,P)$ 。

https://www.luogu.com.cn/paste/mapg8dc2