最幸运的数字
$8$ 是中国的幸运数字，如果一个数字的每一位都由 $8$ 构成则该数字被称作是幸运数字。
现在给定一个正整数 $L$，请问至少多少个 $8$ 连在一起组成的正整数（即最小幸运数字）是 $L$ 的倍数。
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含一个整数 $L$。
当输入用例 $L=0$ 时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出结果占一行。
结果为 Case i: +一个整数 $N$，$N$ 代表满足条件的最小幸运数字的位数。
如果满足条件的幸运数字不存在，则 $N=0$。
数据范围
$1 \leq L \leq 2 \times {10}^9$
输入样例：
8 11 16 0
输出样例：
Case 1: 1 Case 2: 2 Case 3: 0
解题思路
假设最小位数为$x$，那么
$$\begin{align*}
& \ \ \ \ \ \overbrace{8 \ldots 8}^{x} \\\\
&= 8 \times \overbrace{1 \ldots 1}^{x} \\\\
&= 8 \times \frac{\overbrace{9 \ldots 9}^{x}}{9} \\\\
&= 8 \times \frac{10^{x}-1}{9}
\end{align*}$$
因此问题由求最小的$x$满足$L \mid \overbrace{8 \ldots 8}^{x}$等价变成了求最小的$x$满足$L \mid 8 \times \dfrac{10^{x}-1}{9}$。
\begin{align*}
& \ \ \ \ \ \ L \mid \overbrace{8 \ldots 8}^{x} \\\\
&\Leftrightarrow L \mid 8 \times \frac{10^{x}-1}{9} \\\\
&\Leftrightarrow 9L \mid 8 \times \left( {{10}^{x}-1} \right) \\\\
&\Leftrightarrow \frac{9L}{\gcd(9L,8)} \mid \frac{8}{\gcd(9L,8)} \times \left( {{10}^{x}-1} \right) \\\\
&\Leftrightarrow \frac{9L}{\gcd(9L,8)} \mid \left( {{10}^{x}-1} \right) \\\\
&\Leftrightarrow C \mid \left( {{10}^{x}-1} \right) ~~~~~~ {\color{red} {\text{note:}}} \ \ C:= \frac{9L}{\gcd(9L,8)} \\\\
&\Leftrightarrow {10}^{x} \equiv 1 \pmod{C}
\end{align*}
对于${10}^{x} \equiv 1 \pmod{C}$，由欧拉定理，如果$\gcd(a, n) = 1$则$a^{\varphi(n)} \equiv 1 \pmod{n}$，如果$\gcd(10, C) \ne 1$那么无解（可以由裴蜀定理来证明），否则必然有解$x$可以取$\varphi(C)$。但题目要求最小的$x$，$\varphi(C)$虽然满足这个同余式但不一定是最小的$x$。
实际上还有一个结论：所有满足同余方程${10}^{x} \equiv 1 \pmod{C}$的最小的正整数$x$一定满足$x \mid \varphi(C)$。因此可以对$\varphi(C)$进行约数分解，把所有约数带到这个同余式找到满足方程的最小的约数。
更一般的，$10$可以换成任意与$C$互质的数$a$，那么所有满足同余方程${a}^{x} \equiv 1 \pmod{C}$的最小的正整数$x$一定满足$x \mid \varphi(C)$。
下面证明这个结论。假设$x$是满足同余方程的最小值且$x \nmid \varphi(C)$，那么$\varphi(C)$一定可以表示成$\varphi(C) = k \cdot x + r$ $(0 < r < x)$。由于${a}^{x} \equiv 1 \pmod{C}$，因此${a}^{k \cdot x} \equiv 1 \pmod{C}$，所以
\begin{align*}
{a}^{\varphi(C)} &\equiv 1 \pmod{C} \\\\
\Leftrightarrow {a}^{k \cdot x + r} &\equiv 1 \pmod{C} \\\\
\Leftrightarrow \ \ \ \ \ \ {a}^{r} &\equiv 1 \pmod{C} \\\\
\end{align*}
因此这样就找到一个新的$r$ $(0 < r < x)$使得${a}^{r} \equiv 1 \pmod{C}$，且$r$比$x$更小，就矛盾了。
总结一下这题的流程步骤，先求出$C = \frac{9L}{\gcd(9L,8)}$，然后判断$10$和$C$是否互质，如果不互质那就无解。否则求出$\varphi(C)$，对$\varphi(C)$分解约数并通过快速幂求满足${10}^{x} \equiv 1 \pmod{C}$的最小约数。
还有一个地方需要注意的是，由于$C$最大可以取到$1.8 \times {10}^{10}$（大概），因此在快速幂中两个数相乘是可能爆$\text{long long}$的，因此还要写个龟速乘来求两个数的乘积。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 LL gcd(LL a, LL b) {
7 return b ? gcd(b, a % b) : a;
8 }
9
10 LL phi(LL x) {
11 LL ret = x;
12 for (int i = 2; i <= x / i; i++) {
13 if (x % i == 0) {
14 ret -= ret / i;
15 while (x % i == 0) {
16 x /= i;
17 }
18 }
19 }
20 if (x > 1) ret -= ret / x;
21 return ret;
22 }
23
24 LL qmul(LL a, LL k, LL p) {
25 LL ret = 0;
26 while (k) {
27 if (k & 1) ret = (ret + a) % p;
28 a = (a + a) % p;
29 k >>= 1;
30 }
31 return ret;
32 }
33
34 LL qmi(LL a, LL k, LL p) {
35 LL ret = 1;
36 while (k) {
37 if (k & 1) ret = qmul(ret, a, p); // ret*a可能会爆long long，因此用龟速乘
38 a = qmul(a, a, p); // 同理
39 k >>= 1;
40 }
41 return ret;
42 }
43
44 int main() {
45 int tot = 1;
46 LL l;
47 while (scanf("%lld", &l), l) {
48 LL c = 9 * l / gcd(9 * l, 8), ret = 1e18;
49 if (gcd(10, c) != 1) { // 10和c不互质，无解
50 ret = 0;
51 }
52 else {
53 LL phi_c = phi(c);
54 for (int i = 1; i <= phi_c / i; i++) { // 分解phi(c)的约数
55 if (phi_c % i == 0) {
56 if (qmi(10, i, c) == 1) ret = min(ret, (LL)i); // 约数满足同余式则求最小的约数
57 if (qmi(10, phi_c / i, c) == 1) ret = min(ret, phi_c / i); // 另外一个约数
58 }
59 }
60 }
61 printf("Case %d: %lld\n", tot++, ret);
62 }
63
64 return 0;
65 }
参考资料
AcWing 202. 最幸运的数字（算法提高课）：https://www.acwing.com/video/705/
标签：10,数字,pmod,LL,ret,varphi,幸运,equiv From： https://www.cnblogs.com/onlyblues/p/17069969.html