求解满足 $L | \begin{matrix}\underbrace{8\cdots8}\\\x\end{matrix}$ 的最小正整数 $x$

对右边式子进行构造：

$8 \cdots 8 = 8 \times 1 \cdots 1 = 8 \times \dfrac{9 \cdots 9}{9} = 8 \times \dfrac{10^x - 1}{9}$

于是原问题就变成了求解满足 $9L~| 8 \times (10^x - 1)$ 的最小正整数 $x$

由于 $8$ 和 $9$ 互质，我们设 $d = gcd(L, 8)$

继续化简 $\dfrac{9L}{d} | (10^x - 1)$

这一步不懂得可以看到这来
$$ 先不妨令A = 10^x-1,则 9L\Big|8A\\\又因为gcd(8,9)=1,所以设gcd(9L,8)=gcd(L,8)=d\\\于是\frac{9L}{d}\Big|\frac{8}{d}\cdot A\\\又因为gcd(\frac{9L}{d},\frac{8}{d})=gcd(\frac{L}{d},\frac{8}{d})=1\\\故\frac{9L}{d}\Big|A $$

令 $C = \dfrac{9L}{d}$，则变成 $C | (10^x - 1)$

最终变成求解满足 $10^x \equiv 1 \pmod{C}$ 的最小正整数 $x$

这里的形式有点像欧拉定理: $a^{\varphi(c)} \equiv 1 \pmod{c} \quad(其中 gcd(a,c) = 1)$

但是欧拉定理不能保证 $\varphi(n)$ 是满足等式的最小正整数

此处有一个结论：满足上述式子的最小正整数 $x$ 一定是 $\varphi(c)$ 的约数，即 $x | \varphi(c)$
反证法：假设该最小正整数 $x$ 不是 $\varphi(c)$ 的约数
则 $\varphi(c) = qx + r \quad(0\lt r \lt x)$，
又 $\begin{cases}10^x\equiv1\pmod{c}\Rightarrow 10^{qx}\equiv1\pmod{c}\\\ 10^{\varphi(c)}\equiv1\pmod{c} \Rightarrow 10^{qx + r}\equiv1\pmod{c}\end{cases}$
由$2$式除以$1$式得 $10^{r}\equiv1\pmod{c} \quad(0\lt r \lt x)$
故存在比 $x$ 更小的正整数满足该式子，矛盾了
因此得证

接下来只需暴力枚举出 $\varphi(c)$ 的所有约数，找出满足条件的最小正整数 $x$ 即可。

#include <iostream>

using namespace std;

typedef long long LL;

//欧几里得算法
int gcd(LL a, int b) {
    return b ? gcd(b, a % b) : a;
}
//试除法求欧拉函数
LL get_euler(LL c) {
    LL res = c;
    for (int i = 2; i <= c / i; ++ i) {
        if (c % i == 0) {
            int s = 0;
            while (c % i == 0) ++ s, c /= i;
            res = res / i * (i - 1);
        }
    }
    if (c > 1) res = res / c * (c - 1);
    return res;
}
//龟速乘
LL qmul(LL a, LL b, LL c) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return res;
}
//快速幂
LL qmi(LL a, LL b, LL c) {
    LL res = 1;
    while (b) {
        if (b & 1) res = qmul(res, a, c);
        a = qmul(a, a, c);
        b >>= 1;
    }
    return res;
}
int main() {
    int T = 1;
    LL L;
    while (cin >> L, L) {
        int d = gcd(L, 8);

        LL c = 9 * L / d;

        LL phi = get_euler(c);

        LL res = 1e18;
        if (c % 2 == 0 || c % 5 == 0) res = 0; //判断c和10是否互质(10必须模c余1)
        else {
            for (LL i = 1; i <= phi / i; ++ i) {
                if (phi % i == 0) {
                    if (qmi(10, i, c) == 1) res = min(res, i);
                    if (qmi(10, phi / i, c) == 1) res = min(res, phi / i);
                }
            }
        }
        printf("Case %d: %lld\n", T ++ , res);
    }
    return 0;
}