「The Luckiest Number」最幸运的数字

形式化题目

记 $R_n = \underbrace{88\cdots8}_{n\ \text{位}} = \dfrac{8(10^n-1)}{9}$ 。给定正整数 $L$ ，求最小的 $n \ge 1$ 使 $L \mid R_n$ ；若不存在这样的 $n$ ，答案为 $0$ 。

正解

思路

答案是位数 $n$ ，而 $n$ 可以极大：真实数据里 $L = 12984753$ 的答案是 $31920$ ；再试几个 $10^9$ 量级的 $L$ ，答案轻易升到 $10^8$ 量级（例如 $L = 1999999999$ 时是 $161290320$ ）。所以既不能逐位拼出 $88\cdots8$ 再取模，也不能把 $n$ 当成搜索变量去试。必须把"最小 $n$ "一次算出来。

第一步：把 $R_n$ 写成闭式。 $n$ 位全 8 数就是 $\dfrac{8(10^n-1)}{9}$ ，于是

L \mid \frac{8(10^n-1)}{9} \iff 9L \mid 8(10^n-1).

第二步：约掉公共因子。 令 $g = \gcd(9L, 8) = \gcd(L, 8)$ ，两边同除以 $g$ ，整除条件不变形为

m \mid 10^n-1, \qquad m = \frac{9L}{g}.

第三步：认出这是"阶"。 $m \mid 10^n-1$ 就是 $10^n \equiv 1 \pmod m$ 。要求的"最小 $n$ "正是 $10$ 模 $m$ 的乘法阶 $\operatorname{ord}_m(10)$ 。同余式有解当且仅当 $\gcd(10, m) = 1$ ：若 $m$ 含因子 $2$ 或 $5$ ，则 $10^n$ 与 $m$ 不互素， $10^n \equiv 1$ 永远不成立，此时输出 $0$ 。

第四步：把候选集缩到 $\varphi(m)$ 的因数。 欧拉定理给出 $10^{\varphi(m)} \equiv 1 \pmod m$ ；把" $a^k \equiv 1$ 的解集恰是阶的倍数集"这条性质用在 $k = \varphi(m)$ 上，就得到

\operatorname{ord}_m(10) \mid \varphi(m).

于是把 $m$ 试除分解一次算出 $\varphi(m)$ ，再把 $\varphi(m)$ 分解一次列出它的全部因数（升序），从小到大对每个因数 $d$ 做一次快速幂 pow(10, d, m)，第一个等于 $1$ 的 $d$ 就是答案。因数个数只有千级，全部验证也不过几千次模幂，而 $\sqrt{m}$ 的试除也只有 $1.3 \times 10^5$ 次循环。

下图是上面四步的等价变形链：

flowchart TD
    A["L 整除 8(10^n-1)/9"] -->|"两边乘 9"| B["9L 整除 8(10^n-1)"]
    B -->|"除以 g = gcd(L,8)"| C["m = 9L/g 整除 10^n-1"]
    C --> D["10^n 同余 1 mod m"]
    D --> E{"gcd(m,10) 等于 1 ?"}
    E -->|"否"| F["答案 0"]
    E -->|"是"| G["n 就是 10 模 m 的阶"]
    G -->|"阶整除 phi(m)"| H["枚举 phi(m) 的因数 d，<br>取最小的使 pow(10,d,m) 等于 1 的 d"]

每个箭头都是一次可逆的等价变形，因此链尾的 $n$ 与题目要求的最小位数逐字对应；分岔点只有" $10$ 与 $m$ 是否互素"一处。

用真实数据里的几个用例核对每一步的数值：

$L$	$g=\gcd(L,8)$	$m=9L/g$	$\gcd(m,10)$	$\varphi(m)$	最小可行 $d$
$8$	$8$	$9$	$1$	$6$	$d=1$
$11$	$1$	$99$	$1$	$60$	$d=2$
$16$	$8$	$18$	$2$	不计算	无解，输出 $0$
$82$	$2$	$369$	$1$	$240$	$d=5$
$540$	$4$	$1215$	$5$	不计算	无解，输出 $0$

表中三个有解用例的答案依次是 $1, 2, 5$ ：前两个就是题面样例 8、11 的输出， $5$ 与真实数据 data/0.out 中 $L=82$ 一行一致；剩下两行无解，对应样例里输出 $0$ 的 16。 $L=82$ 那一行可以手工验证： $10^5 = 100000 = 271 \times 369 + 1$ ，而 $d=1,2,3,4$ 时 $10^d \bmod 369 = 10, 100, 262, 37$ ，都不为 $1$ ，所以 $5$ 就是阶。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:14
# update_at: 2026-10-01 16:20

from math import gcd
from sys import stdin


def factorize(n: int) -> list[tuple[int, int]]:
    """返回 n 的质因数分解 [(p, e), ...]：试除到 sqrt(n)，余数大于 1 时本身就是质因子。"""
    factors, p = [], 2
    while p * p <= n:
        if n % p == 0:
            e = 0
            while n % p == 0:
                n //= p
                e += 1
            factors.append((p, e))
        p += 1
    return factors + ([(n, 1)] if n > 1 else [])


def euler_phi(factors: list[tuple[int, int]]) -> int:
    """由质因数分解算 phi(n) = prod (p-1) * p^(e-1)。"""
    phi = 1
    for p, e in factors:
        phi *= (p - 1) * p ** (e - 1)
    return phi


def all_divisors(factors: list[tuple[int, int]]) -> list[int]:
    """由质因数分解升序生成全部正因数。"""
    divisors = [1]
    for p, e in factors:
        divisors = [d * p ** k for d in divisors for k in range(e + 1)]
    return sorted(divisors)


def multiplicative_order(a: int, mod: int) -> int:
    """返回 a 模 mod 的阶（最小的 n 使 a^n ≡ 1），调用前保证 gcd(a, mod) = 1。

    欧拉定理给出 a^phi ≡ 1，而 a^k ≡ 1 的解集是阶的倍数集，故阶必整除 phi；
    在 phi 的升序因数里取第一个可行者即为阶。
    """
    phi = euler_phi(factorize(mod))
    return next(d for d in all_divisors(factorize(phi)) if pow(a, d, mod) == 1)


def smallest_lucky_length(L: int) -> int:
    """L 的倍数中最小的全 8 数的位数；不存在这样的数时返回 0。"""
    # n 位全 8 数 = 8*(10^n - 1)/9，条件 L | 8*(10^n - 1)/9 等价于 9L/g | (10^n - 1)，
    # 其中 g = gcd(9L, 8) = gcd(L, 8)；于是问题变成 10^n ≡ 1 (mod 9L/g) 的最小 n。
    m = 9 * L // gcd(L, 8)
    return 0 if gcd(m, 10) != 1 else multiplicative_order(10, m)


def solve() -> None:
    out: list[str] = []
    case = 0
    for L in map(int, stdin.buffer.read().split()):
        if L == 0:  # 0 是输入终止标记，本身不处理
            break
        case += 1
        out.append(f"Case {case}: {smallest_lucky_length(L)}")
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:11
 * update_at: 2026-10-06 18:11
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXF = 64;          // 一个数的不同质因子个数上限，远小于 64
const int MAXDIV = 100000;    // phi(m) 的因数个数上限，1.8e10 内最多几千个

ll fac_p[MAXF];               // 当前分解结果里的质因子
int fac_e[MAXF];              // 与 fac_p 对应的指数
int fac_cnt;                  // 当前分解结果里的不同质因子个数

ll divs[MAXDIV];              // phi(m) 的全部正因数，生成后排序
int div_cnt;

// 试除分解 n，结果写入 fac_p / fac_e，并把 fac_cnt 置为质因子个数。
void factorize(ll n) {
    fac_cnt = 0;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int e = 0;
            while (n % p == 0) {
                n /= p;
                e++;
            }
            fac_p[fac_cnt] = p;
            fac_e[fac_cnt] = e;
            fac_cnt++;
        }
    }
    if (n > 1) { // 剩下的 n 本身是质因子
        fac_p[fac_cnt] = n;
        fac_e[fac_cnt] = 1;
        fac_cnt++;
    }
}

// 用当前 fac_p / fac_e 计算欧拉函数 phi(n) = 乘积 (p-1) * p^(e-1)。
ll euler_phi() {
    ll phi = 1;
    for (int i = 0; i < fac_cnt; i++) {
        ll p = fac_p[i];
        int e = fac_e[i];
        for (int j = 0; j < e - 1; j++) {
            phi *= p;
        }
        phi *= (p - 1);
    }
    return phi;
}

// 递归展开当前 fac_p / fac_e 的全部正因数，存入 divs。
void gen_divisors(int idx, ll cur) {
    if (idx == fac_cnt) {
        divs[div_cnt] = cur;
        div_cnt++;
        return;
    }
    ll val = cur;
    for (int k = 0; k <= fac_e[idx]; k++) {
        gen_divisors(idx + 1, val);
        val *= fac_p[idx];
    }
}

// 计算 a * b % mod；m 可达 1.8e10，直接相乘会溢出 ll，所以借用 __int128。
ll mul_mod(ll a, ll b, ll mod) {
    __int128 t = (__int128)a * b; // 与 __int128 对接必须显式转换
    return (ll)(t % mod);
}

// 快速幂：返回 a^e % mod。
ll pow_mod(ll a, ll e, ll mod) {
    ll res = 1 % mod;
    a %= mod;
    while (e > 0) {
        if (e & 1) {
            res = mul_mod(res, a, mod);
        }
        a = mul_mod(a, a, mod);
        e >>= 1;
    }
    return res;
}

// 求 10 模 m 的乘法阶（调用前保证 gcd(10, m) = 1）。
// 阶整除 phi(m)，故在 phi(m) 的升序因数中取第一个使 10^d ≡ 1 的 d。
ll multiplicative_order(ll mod) {
    factorize(mod);
    ll phi = euler_phi();

    factorize(phi);
    div_cnt = 0;
    gen_divisors(0, 1);
    sort(divs, divs + div_cnt);

    for (int i = 0; i < div_cnt; i++) {
        if (pow_mod(10, divs[i], mod) == 1) {
            return divs[i];
        }
    }
    return phi;
}

// 返回 L 的最小全 8 倍数位数；不存在时返回 0。
ll smallest_lucky_length(ll L) {
    // n 位全 8 数 = 8(10^n-1)/9，于是 9L | 8(10^n-1)；
    // 约去 g = gcd(9L,8) = gcd(L,8) 后化为 10^n ≡ 1 (mod 9L/g)。
    ll m = 9 * L / gcd(L, 8LL);
    if (gcd(m, 10LL) != 1) { // m 含因子 2 或 5 时无解
        return 0;
    }
    return multiplicative_order(m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll L;
    int case_id = 0;
    while (cin >> L && L != 0) {
        case_id++;
        cout << "Case " << case_id << ": " << smallest_lucky_length(L) << "\n";
    }
    return 0;
}

factorize 做一次 $O(\sqrt{n})$ 的试除， $\varphi(m)$ 和 $m$ 的因数表都只在这份分解上做乘积与笛卡尔展开；multiplicative_order 里再对 $\varphi(m)$ 分解一次，然后把"升序因数 + pow 验证"压成一行 next(...)，升序由 all_divisors 末尾的 sorted 保证。

复杂度

单组测试的瓶颈是两次 $O(\sqrt{n})$ 的质因数分解：一次分解 $m = \dfrac{9L}{\gcd(L,8)} \le 1.8 \times 10^{10}$ ，约 $1.3 \times 10^5$ 次循环；一次分解 $\varphi(m) < m$ ，同量级。因数表由分解结果直接展开。随后对 $\varphi(m)$ 的每个因数做一次快速幂，共 $O(d(\varphi(m)) \log \varphi(m))$ 次模乘，因数个数为千级。总时间 $O(T\sqrt{L})$ ，空间 $O(d(\varphi(m)))$ 。与逐位模拟的 $O(\text{答案})$ 相比，把搜索量从 $10^8$ 量级降到了 $10^5$ 量级。

总结

题目问"多少个 $8$ 连起来能被 $L$ 整除"，直接逐位拼数会死在位数上。把它化成 $10^n \equiv 1 \pmod m$ 之后，“最小的 $n$ ” 就是 $10$ 模 $m$ 的乘法阶；再用阶整除 $\varphi(m)$ 这一性质把候选集压缩到 $\varphi(m)$ 的因数，配合快速幂，整个问题只需两次 $O(\sqrt{L})$ 量级的试除分解。两个易错点：约分时要用 $\gcd(9L,8)=\gcd(L,8)$ 而不是 $\gcd(L,9)$ ；判定无解要用 $\gcd(m,10)=1$ ，这正好覆盖了 $16$ 、 $540$ 这类含因子 $2$ 或 $5$ 的用例。

「The Luckiest Number」 最幸运的数字

目录

形式化题目

正解

思路

代码

复杂度

总结

「The Luckiest Number」最幸运的数字