循环节

[题目链接](https://www.nowcoder.com/practice/b1b3a5610b3147fb80eb1c273983e936)

思路

题意是：给定正整数 $n$ ，求 $1/n$ 表示成小数时，循环节的最短长度。如果 $1/n$ 是有限小数，输出 1。

先回忆一下小数除法的过程。我们做 $1 \div n$ 的竖式除法时，每一步把余数乘以 10 再除以 $n$ ，得到商的一位小数。什么时候开始循环？当某个余数再次出现时，后面的过程就会完全重复。

所以暴力做法是模拟长除法、记录余数，找到循环。但 $n$ 可以到 $10^9$ ，循环节长度最多是 $n-1$ ，暴力模拟会超时。

那怎么优化呢？我们来用数论的视角重新看这个问题。

$1/n$ 的小数部分会循环，本质上是因为余数序列 $10^0, 10^1, 10^2, \ldots$ 对 $n$ 取模是周期性的。循环节长度就是最小的正整数 $k$ ，使得 $10^k \equiv 1 \pmod{n}$ 。这在数论中叫做 10 模 $n$ 的乘法阶（multiplicative order）。

不过这有个前提： $\gcd(10, n) = 1$ 。如果 $n$ 含有因子 2 或 5， $1/n$ 的小数会有一段非循环的"前导部分"，但循环节只取决于去掉 2 和 5 之后的部分。所以我们先把 $n$ 中的 2 和 5 全部除掉，得到 $n'$ 。如果 $n' = 1$ ，说明 $1/n$ 是有限小数，输出 1。

接下来就是求 $\text{ord}_{n'}(10)$ 。根据欧拉定理， $10^{\varphi(n')} \equiv 1 \pmod{n'}$ ，所以阶一定整除 $\varphi(n')$ 。算法是：

计算 $\varphi(n')$ （欧拉函数）
对 $\varphi(n')$ 做质因数分解
从 $\text{order} = \varphi(n')$ 开始，依次尝试每个质因子 $p$ ：如果 $10^{\text{order}/p} \equiv 1 \pmod{n'}$ ，就把 order 除以 $p$ ，重复直到不能再除

这样就能高效地求出最小的阶了。时间瓶颈在于对 $n'$ 和 $\varphi(n')$ 做试除法分解，复杂度 $O(\sqrt{n})$ ，完全够用。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

ll powmod(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

vector<pair<ll,int>> factorize(ll n) {
    vector<pair<ll,int>> res;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }
            res.push_back({i, cnt});
        }
    }
    if (n > 1) res.push_back({n, 1});
    return res;
}

ll euler_phi(ll n) {
    ll res = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res = res / i * (i - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

ll mult_order(ll n) {
    ll phi = euler_phi(n);
    auto factors = factorize(phi);
    ll order = phi;
    for (auto& [p, e] : factors) {
        while (order % p == 0 && powmod(10, order / p, n) == 1) {
            order /= p;
        }
    }
    return order;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        while (n % 2 == 0) n /= 2;
        while (n % 5 == 0) n /= 5;
        if (n == 1) {
            cout << 1 << "\n";
        } else {
            cout << mult_order(n) << "\n";
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static long powmod(long a, long b, long m) {
        long res = 1;
        a %= m;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % m;
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }

    static long eulerPhi(long n) {
        long res = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                res = res / i * (i - 1);
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    }

    static long[][] factorize(long n) {
        List<long[]> factors = new ArrayList<>();
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int cnt = 0;
                while (n % i == 0) { n /= i; cnt++; }
                factors.add(new long[]{i, cnt});
            }
        }
        if (n > 1) factors.add(new long[]{n, 1});
        return factors.toArray(new long[0][]);
    }

    static long multOrder(long n) {
        long phi = eulerPhi(n);
        long[][] factors = factorize(phi);
        long order = phi;
        for (long[] f : factors) {
            long p = f[0];
            while (order % p == 0 && powmod(10, order / p, n) == 1) {
                order /= p;
            }
        }
        return order;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            while (n % 2 == 0) n /= 2;
            while (n % 5 == 0) n /= 5;
            if (n == 1) {
                sb.append(1).append('\n');
            } else {
                sb.append(multOrder(n)).append('\n');
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def factorize(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            factors.append((i, cnt))
        i += 1
    if n > 1:
        factors.append((n, 1))
    return factors

def euler_phi(n):
    res = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            res = res // i * (i - 1)
        i += 1
    if n > 1:
        res = res // n * (n - 1)
    return res

def mult_order(n):
    phi = euler_phi(n)
    factors = factorize(phi)
    order = phi
    for p, _ in factors:
        while order % p == 0 and pow(10, order // p, n) == 1:
            order //= p
    return order

T = int(input())
out = []
for _ in range(T):
    n = int(input())
    while n % 2 == 0:
        n //= 2
    while n % 5 == 0:
        n //= 5
    if n == 1:
        out.append('1')
    else:
        out.append(str(mult_order(n)))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const T = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < T; i++) {
        let n = BigInt(lines[idx++]);
        while (n % 2n === 0n) n /= 2n;
        while (n % 5n === 0n) n /= 5n;
        if (n === 1n) {
            out.push('1');
        } else {
            out.push(String(multOrder(n)));
        }
    }
    console.log(out.join('\n'));
});

function powmod(a, b, m) {
    let res = 1n;
    a = a % m;
    while (b > 0n) {
        if (b & 1n) res = res * a % m;
        a = a * a % m;
        b >>= 1n;
    }
    return res;
}

function eulerPhi(n) {
    let res = n;
    for (let i = 2n; i * i <= n; i++) {
        if (n % i === 0n) {
            while (n % i === 0n) n /= i;
            res = res / i * (i - 1n);
        }
    }
    if (n > 1n) res = res / n * (n - 1n);
    return res;
}

function factorize(n) {
    const factors = [];
    for (let i = 2n; i * i <= n; i++) {
        if (n % i === 0n) {
            let cnt = 0;
            while (n % i === 0n) { n /= i; cnt++; }
            factors.push([i, cnt]);
        }
    }
    if (n > 1n) factors.push([n, 1]);
    return factors;
}

function multOrder(n) {
    let phi = eulerPhi(n);
    const factors = factorize(phi);
    let order = phi;
    for (const [p, _] of factors) {
        while (order % p === 0n && powmod(10n, order / p, n) === 1n) {
            order /= p;
        }
    }
    return order;
}

复杂度分析

时间复杂度： $O(\sqrt{n} \cdot \log n)$ 。对每个 $n$ ，试除法分解 $n'$ 和 $\varphi(n')$ 各需要 $O(\sqrt{n})$ ，求阶的过程中快速幂每次 $O(\log n)$ ，质因子个数不超过 $O(\log n)$ ，总计 $O(\sqrt{n} + \log^2 n) = O(\sqrt{n})$ 。
空间复杂度： $O(\log n)$ ，存储质因数分解结果。