题解 | #循环节#

题目链接

题目描述

求分数 $1/N$ 表示为循环小数时，其循环节的长度。注意：可以用有限数表示的数的循环节的长度为1。

解题思路

本题要求计算分数 $1/N$ 的循环节长度，且 $N$ 的范围很大（最高可达 $10^9$ ），因此直接模拟长除法会超时。正确的解法需要运用数论知识。

1. 问题转化与数论基础

分数 $1/N$ 的小数表示的循环节长度，本质上是求满足 $10^k \equiv 1 \pmod{N'}$ 的最小正整数 $k$ 。

这里的 $N'$ 是将原分母 $N$ 中所有与基数 $10$ 共享的质因子（即 $2$ 和 $5$ ）都除去后得到的新分母。这是因为因子 $2$ 和 $5$ 只会影响小数的不循环部分，而循环部分完全由与 $10$ 互质的因子 $N'$ 决定。

2. 处理有限小数

我们首先计算 $N'$ ：不断将 $N$ 除以 $2$ 和 $5$ 直到它不再能被这两者整除。

如果最终得到的 $N'$ 等于 $1$ ，说明 $N$ 的所有质因子仅包含 $2$ 和 $5$ 。这意味着 $1/N$ 是一个有限小数。
根据题目的特殊规定：“可以用有限数表示的数的循环节的长度为1”，此时我们应输出 $1$ 。

3. 求解循环节长度（乘法阶）

如果 $N' > 1$ ，问题就变成了求 $10$ 模 $N'$ 的乘法阶（Order）。

根据欧拉定理，我们知道 $10^{\phi(N')} \equiv 1 \pmod{N'}$ ，其中 $\phi(N')$ 是欧拉函数，表示小于 $N'$ 且与 $N'$ 互质的正整数的个数。
这个定理告诉我们，我们要求的最小的 $k$ 一定是 $\phi(N')$ 的一个因子。
因此，我们的算法步骤如下： a. 计算 $N'$ 。 b. 计算欧拉函数值 phi_N_prime = $\phi(N')$ 。 c. 找出 phi_N_prime 的所有因子。 d. 将这些因子从小到大排序。 e. 遍历每一个因子 $d$ ，使用快速幂算法检查是否 $10^d \pmod{N'} == 1$ 。 f. 第一个满足该条件的因子 $d$ 就是我们要求的最小循环节长度。

这个方法将问题从模拟计算转变为数论函数的计算，效率足以通过本题。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

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

void solve() {
    long long n;
    cin >> n;
    while (n % 2 == 0) n /= 2;
    while (n % 5 == 0) n /= 5;

    if (n == 1) {
        cout << 1 << endl;
        return;
    }

    long long euler_phi = phi(n);
    vector<long long> divisors;
    for (long long i = 1; i * i <= euler_phi; ++i) {
        if (euler_phi % i == 0) {
            divisors.push_back(i);
            if (i * i != euler_phi) {
                divisors.push_back(euler_phi / i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());

    for (long long d : divisors) {
        if (power(10, d, n) == 1) {
            cout << d << endl;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        long n = sc.nextLong();
        while (n % 2 == 0) n /= 2;
        while (n % 5 == 0) n /= 5;

        if (n == 1) {
            System.out.println(1);
            return;
        }

        long eulerPhi = phi(n);
        List<Long> divisors = getDivisors(eulerPhi);
        Collections.sort(divisors);

        for (long d : divisors) {
            if (power(10, d, n) == 1) {
                System.out.println(d);
                return;
            }
        }
    }

    private static long phi(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }
    
    private static List<Long> getDivisors(long n) {
        List<Long> divisors = new ArrayList<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
                if (i * i != n) {
                    divisors.add(n / i);
                }
            }
        }
        return divisors;
    }

    private static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}

import sys

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def get_divisors(n):
    divs = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divs.append(i)
            if i*i != n:
                divs.append(n//i)
    divs.sort()
    return divs

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)

    while n % 2 == 0:
        n //= 2
    while n % 5 == 0:
        n //= 5

    if n == 1:
        print(1)
        return

    euler_phi = phi(n)
    divisors = get_divisors(euler_phi)

    for d in divisors:
        if power(10, d, n) == 1:
            print(d)
            return

def main():
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论（欧拉定理、乘法阶）
时间复杂度： $\mathcal{O}(\sqrt{N})$ 。主要开销来自于计算欧拉函数 $\phi(N')$ 和寻找 $\phi(N')$ 的因子，这两者的复杂度都是根号级别的。之后遍历因子并进行快速幂的计算，其复杂度远小于前者。
空间复杂度： $\mathcal{O}(d(\phi(N')))$ ，其中 $d(k)$ 是 $k$ 的因子数量，这个值增长非常缓慢，远小于 $N$ 。