P1050 [NOIP 2005 普及组] 循环

题目解读

给定一个非常大的整数 $n$ 和一个小整数 $k$，要求计算 $n$ 的正整数次幂 $n^a$ 的 最后 $k$ 位 数字，且这些最后 $k$ 位数字是否会存在某种 循环规律。如果存在这样的循环规律，要求输出 最小的循环长度，如果没有循环规律，则输出 -1。

让我们来看样例

• 输入：n = 32, k = 2
• 输出：4

列个表格：

从表格中可以看到：

• 当 a=1 时，余数为 32。
• 当 a=2 时，余数为 24。
• 当 a=3 时，余数为 68。
• 当 a=4 时，余数为 76。
• 当 a=5 时，余数再次变为 32，与 a=1 时相同，开始循环。

此后余数序列重复：32 → 24 → 68 → 76 → 32 → …，循环长度为 4。

知识铺垫

1. 快速幂

问题： 计算 $ n^a \mod 10^k $，如果 $ a $ 很大，直接乘 $ a $ 次会超慢。

快速幂的核心思想：把指数 $ a $ 拆成二进制（就像折纸一样，反复对折），用平方和乘法代替重复乘法。这样能把计算次数从 $ O(a) $ 降到 $ O(\log a) $。

证明

任何指数 $ a $ 可以转换为二进制，这相当于 $ a = 2^{k_1} + 2^{k_2} + \cdots $。

计算 $ n^a $ 时，因为乘法有分配律，我们可以将问题转化为 $ n^1 \times n^2 \times n^4 \times n^8 \times \ldots $。

2. 阶：

在模运算中，幂的结果会循环。阶就是这个循环的最小周期。以样例 $ 32 $ 为例，他的阶就是 $ 4 $。

具体运用

• 如果知道阶 $d$（循环周期），当 $n^{d} \equiv 1 \pmod{m}$ 时，我们可以构造以下式子：

$$ \begin{aligned} n^{d+1} &\equiv n^d \cdot n \equiv 1 \cdot n \equiv n \pmod{m}, \\ n^{d+2} &\equiv n^d \cdot n^2 \equiv 1 \cdot n^2 \equiv n^2 \pmod{m}, \\ &\quad \vdots \\ n^{d+k} &\equiv n^k \pmod{m}. \end{aligned} $$

• 由这个式子，我们可以得出 $ n^{a} \equiv n^{a \mod d} \pmod{m} $，将大指数 $ a $ 缩小到 $ a \mod d $。

找阶的方法

• 条件： $n$ 和模数 $m$ 必须互质，即最大公约数 $\gcd(n, m) = 1$。因为这道题中 $m = 10^k$，所以要求 $n$ 不能被 2 或 5 整除。

• 欧拉定理： 如果 $\gcd(n, m) = 1$，则 $n^{\phi(m)} \equiv 1 \pmod{m}$。$\phi(m)$ 是小于 $m$ 且与 $m$ 互质的数的个数。

• 欧拉函数 $\phi(n)$ 的定义： 对于正整数 $n$，欧拉函数 $\phi(n)$ 表示小于或等于 $n$ 的正整数中与 $n$ 互质的数的个数。如果 $n$ 有标准质因数分解：

  $$ n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} $$

  那么：

  $$ \phi(n) = n \left(1 – \frac{1}{p_1}\right)\left(1 – \frac{1}{p_2}\right) \cdots \left(1 – \frac{1}{p_m}\right) $$

• 应用于 $m = 10^k$： 首先对 $10^k$ 进行质因数分解：

  $$ 10^k = (2 \times 5)^k = 2^k \times 5^k. $$

  因此，$10^k$ 的质因数为 2 和 5。代入欧拉函数公式：

  $$ \phi(10^k) = 10^k \left(1 – \frac{1}{2}\right)\left(1 – \frac{1}{5}\right). $$

  所以：

  $$ \phi(10^k) = 10^k \times \frac{1}{2} \times \frac{4}{5} = 10^k \times \frac{2}{5}. $$

  进一步化简：

  $$ \phi(10^k) = \frac{2}{5} \times 10^k = 4 \times 10^{k-1}. $$

  • 所以对于 $ m = 10^k $，有 $ \phi(10^k) = 10^k \times (1 – \frac{1}{2}) \times (1 – \frac{1}{5}) = 4 \times 10^{k-1} $。

• 阶 $ d $ 的性质： $ d $ 是最小正整数，使得 $ n^d \equiv 1 \pmod{m} $，且 $ d $ 必须整除 $ \phi(m) $。这里就不证明了，感兴趣可以去自行学习。

• 找 $ d $ 的步骤：

  1. 计算 $ \phi(m) $（如 $ m = 10^k $，则 $ \phi(10^k) = 4 \times 10^{k-1} $。
  2. 列出 $ \phi(m) $ 的所有正除数（从小到大）。
  3. 测试最小的除数 $ d $ 满足 $ n^d \equiv 1 \pmod{m} $。 这里注意，由于本题的数据范围极大，第 iii 步需要用快速幂算。

For example

找 $ n = 3 $ 在 $ \mod 100 $（即 $ 10^2 $，$ k=2 $ 下的阶。

• 条件：$ \gcd(3, 100) = 1 $（互质），阶存在。
• 计算 $ \phi(100) = 100 \times (1 – \frac{1}{2}) \times (1 – \frac{1}{5}) = 40 $。
• $ \phi(100) = 40 $ 的除数：1, 2, 4, 5, 8, 10, 20, 40。
• 测试（用快速幂算 $ 3^d \mod 100 $：
  • $ d = 1 $: $ 3^1 = 3 \not\equiv 1 $
  • $ d = 2 $: $ 3^2 = 9 \not\equiv 1 $
  • $ d = 4 $: $ 3^4 = 81 \not\equiv 1 $
  • $ d = 5 $: $ 3^5 = 243 \equiv 43 \not\equiv 1 $
  • $ d = 8 $: $ 3^8 = (3^4)^2 = 81^2 = 6561 \equiv 61 \not\equiv 1 $
  • $ d = 10 $: $ 3^{10} = (3^5)^2 = 243^2 \equiv 43^2 = 1849 \equiv 49 \not\equiv 1 $
  • $ d = 20 $: $ 3^{20} \equiv (3^{10})^2 \equiv 49^2 = 2401 \equiv 1 \pmod{100} $（成立！）
• 所以阶 $ d = 20 $。序列每 20 次幂循环一次（如 $ 3^1 \equiv 03 $, $ 3^2 \equiv 09 $, …, $ 3^{20} \equiv 01 $, $ 3^{21} \equiv 03 $, …）。

结合快速幂和阶计算 $ n^a \mod 10^k $

情况 1：$ n $ 和 $ 10^k $ 互质（即 $ n $ 是奇数且不被 5 整除）

这里由于阶存在，我们可以减少指数大小。 步骤：

1. 找阶 $ d $：
   • 计算 $ \phi(10^k) = 4 \times 10^{k-1} $。
   • 找最小 $ d $（整除 $ \phi(10^k) $ 使得 $ n^d \equiv 1 \pmod{10^k} $。
2. 缩小指数：计算 $ r = a \mod d $。
3. 计算结果：因为 $ n^a \equiv n^r \pmod{10^k} $，所以用快速幂计算 $ n^r \mod 10^k $ 就可以算出结果了。

For example

计算 $ 3^{100} \mod 100 $。

• $ n = 3 $, $ k = 2 $, $ m = 100 $。
• 互质：是（$ \gcd(3, 100) = 1 $。
• 找阶：如前，$ d = 20 $。
• 缩小指数：$ r = 100 \mod 20 = 0 $（当 $ r = 0 $，取 $ n^d \equiv 1 $。
• 结果：$ 3^{100} \equiv 1 \pmod{100} $。

情况 2：$ n $ 和 $ 10^k $ 不互质（即 $ n $ 含因子 2 或 5）

这里由于欧拉定理要求互质，所以阶可能不存在。

• 处理思路： 对于大 $ a $，$ n^a \mod 10^k $ 可能最终为 0（如果 $ n $ 含 2 和 5），或进入一个“稳定循环”。但在实践中，常用以下方法：
  1. 分离因子：把 $ n $ 写成 $ n = 2^p \times 5^q \times m $，其中 $ m $ 与 10 互质。
  2. 计算 $ m^a \mod 10^k $：用情况 1 的方法（阶和快速幂）。
  3. 组合结果：结合因子 $ 2^{p a} $ 和 $ 5^{q a} $ 的影响（可能需额外处理）。

代码设计

大整数处理

由于 $n$ 可能非常大，我们使用字符串来表示 $n$，并通过字符串模拟大整数的加法、乘法和除法操作。

求解过程

• 计算模数：计算 $10^k$（即 $10^k$ 的值）并通过模运算得到结果。
• 逐步计算次幂：通过逐步计算 $n^a \mod 10^k$，记录每次出现的结果并检查是否出现了重复。
• 找最小循环长度：如果某个次幂的结果与之前的结果相同，那么就找到了循环，返回循环长度。

完整代码

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

// 大整数以10^9为基数的高精度表示
const long long BASE = 1000000000;
struct BigInt {
    vector<long long> a; // 低位块在前
    BigInt() {}
    BigInt(long long v) { *this = v; }
    BigInt& operator=(long long v) {
        a.clear();
        if (v > 0) {
            while (v) {
                a.push_back(v % BASE);
                v /= BASE;
            }
        }
        return *this;
    }
};
void trim(BigInt &x) {
    while (!x.a.empty() && x.a.back() == 0) x.a.pop_back();
}
bool isZero(const BigInt &x) { return x.a.empty(); }
int cmpBig(const BigInt &x, const BigInt &y) {
    if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
    for (int i = (int)x.a.size()-1; i >= 0; --i) {
        if (x.a[i] != y.a[i]) return x.a[i] < y.a[i] ? -1 : 1;
    }
    return 0;
}
// 大整数加法
BigInt addBig(const BigInt &x, const BigInt &y) {
    BigInt res;
    long long carry = 0;
    size_t n = max(x.a.size(), y.a.size());
    res.a.resize(n);
    for (size_t i = 0; i < n; i++) {
        long long xi = (i < x.a.size() ? x.a[i] : 0);
        long long yi = (i < y.a.size() ? y.a[i] : 0);
        long long s = xi + yi + carry;
        res.a[i] = s % BASE;
        carry = s / BASE;
    }
    if (carry) res.a.push_back(carry);
    return res;
}
// 大整数减法（假设 x >= y）
BigInt subBig(const BigInt &x, const BigInt &y) {
    BigInt res;
    long long carry = 0;
    size_t n = x.a.size();
    res.a.resize(n);
    for (size_t i = 0; i < n; i++) {
        long long xi = x.a[i], yi = (i < y.a.size() ? y.a[i] : 0);
        long long s = xi - yi - carry;
        if (s < 0) {
            s += BASE; carry = 1;
        } else carry = 0;
        res.a[i] = s;
    }
    trim(res);
    return res;
}
// 大整数乘以小整数
BigInt mulSmall(const BigInt &x, long long m) {
    if (m == 0 || isZero(x)) return BigInt(0);
    BigInt res;
    __int128 carry = 0;
    res.a.resize(x.a.size());
    for (size_t i = 0; i < x.a.size(); i++) {
        __int128 prod = (__int128)x.a[i] * m + carry;
        res.a[i] = (long long)(prod % BASE);
        carry = prod / BASE;
    }
    while (carry) {
        res.a.push_back((long long)(carry % BASE));
        carry /= BASE;
    }
    return res;
}
// 大整数乘法
BigInt mulBig(const BigInt &x, const BigInt &y) {
    if (isZero(x) || isZero(y)) return BigInt(0);
    BigInt res;
    res.a.assign(x.a.size() + y.a.size(), 0);
    for (size_t i = 0; i < x.a.size(); i++) {
        __int128 carry = 0;
        for (size_t j = 0; j < y.a.size() || carry; j++) {
            __int128 cur = res.a[i+j] + (__int128)x.a[i] * (j < y.a.size() ? y.a[j] : 0) + carry;
            res.a[i+j] = (long long)(cur % BASE);
            carry = cur / BASE;
        }
    }
    trim(res);
    return res;
}
// 大整数除以小整数（结果向下取整）
BigInt divSmall(const BigInt &x, int m) {
    BigInt res;
    res.a.resize(x.a.size());
    __int128 carry = 0;
    for (int i = (int)x.a.size() - 1; i >= 0; i--) {
        __int128 cur = x.a[i] + carry * BASE;
        res.a[i] = (long long)(cur / m);
        carry = cur % m;
    }
    trim(res);
    return res;
}
// 大整数对小整数取模
int modSmall(const BigInt &x, int m) {
    __int128 rem = 0;
    for (int i = (int)x.a.size() - 1; i >= 0; i--) {
        rem = (rem * BASE + x.a[i]) % m;
    }
    return (int)rem;
}
// 大整数模运算：返回 a mod m
BigInt modBig(const BigInt &a, const BigInt &m) {
    BigInt res = a;
    if (cmpBig(res, m) < 0) return res;
    int n = (int)res.a.size();
    BigInt cur; cur.a.clear();
    for (int i = n - 1; i >= 0; --i) {
        cur.a.insert(cur.a.begin(), res.a[i]);
        trim(cur);
        long long low = 0, high = BASE - 1, best = 0;
        while (low <= high) {
            long long mid = (low + high) >> 1;
            BigInt prod = mulSmall(m, mid);
            if (cmpBig(prod, cur) <= 0) { best = mid; low = mid + 1; }
            else { high = mid - 1; }
        }
        if (best) {
            BigInt tmp = mulSmall(m, best);
            cur = subBig(cur, tmp);
        }
    }
    trim(cur);
    return cur;
}
// 大整数欧几里得算法求 GCD
BigInt gcdBig(BigInt a, BigInt b) {
    while (!isZero(b)) {
        BigInt r = modBig(a, b);
        a = b; b = r;
    }
    return a;
}
// 大整数快速幂（指数用大数十进制字符串）
BigInt pow_mod_str(BigInt base, string exp, const BigInt &mod) {
    BigInt result(1);
    while (!(exp.size() == 1 && exp[0] == '0')) {
        int last = exp.back() - '0';
        if (last % 2 == 1) {
            BigInt mul = mulBig(result, base);
            result = modBig(mul, mod);
        }
        BigInt sq = mulBig(base, base);
        base = modBig(sq, mod);
        // exp = exp / 2
        int carry = 0;
        for (int i = 0; i < (int)exp.size(); i++) {
            int cur = carry * 10 + (exp[i] - '0');
            exp[i] = (char)('0' + (cur / 2));
            carry = cur % 2;
        }
        while (exp.size() > 1 && exp[0] == '0') exp.erase(exp.begin());
    }
    return result;
}
// 将 BigInt 转为字符串
string toString(const BigInt &x) {
    if (x.a.empty()) return "0";
    string s = to_string(x.a.back());
    for (int i = (int)x.a.size()-2; i >= 0; i--) {
        char buf[16];
        sprintf(buf, "%09lld", x.a[i]);
        s += buf;
    }
    return s;
}

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

    string n;
    int k;
    cin >> n >> k;

    // 统计 n 中因子 2 和 5 的幂次
    int v2 = 0, v5 = 0;
    // 复制字符串来反复整除
    string temp = n;
    // 计算 v2
    while (true) {
        int carry = 0;
        string next;
        next.reserve(temp.size());
        for (char c : temp) {
            int d = c - '0';
            int val = carry * 10 + d;
            next.push_back(char('0' + (val / 2)));
            carry = val % 2;
        }
        if (carry != 0) break; // 不能整除
        v2++;
        // 去除前导零
        size_t pos = next.find_first_not_of('0');
        if (pos == string::npos) { temp = "0"; break; }
        temp = next.substr(pos);
    }
    // 计算 v5
    while (true) {
        int carry = 0;
        string next;
        next.reserve(temp.size());
        for (char c : temp) {
            int d = c - '0';
            int val = carry * 10 + d;
            next.push_back(char('0' + (val / 5)));
            carry = val % 5;
        }
        if (carry != 0) break;
        v5++;
        size_t pos = next.find_first_not_of('0');
        if (pos == string::npos) { temp = "0"; break; }
        temp = next.substr(pos);
    }

    // 如果存在非平凡因子但小于 k，则无全局循环
    if ((v2 > 0 && v2 < k) || (v5 > 0 && v5 < k)) {
        cout << -1;
        return 0;
    }
    // 如果同时 v2>=k 且 v5>=k，则所有幂的后 k 位都为 0，循环长度为 1
    if (v2 >= k && v5 >= k) {
        cout << 1;
        return 0;
    }

    // 辅助函数：计算 n mod M
    auto mod_from_string = [&](const BigInt &M)->BigInt {
        BigInt res(0);
        for (char c : n) {
            res = mulSmall(res, 10);
            BigInt addv(c - '0');
            res = addBig(res, addv);
            if (!isZero(res)) res = modBig(res, M);
        }
        return res;
    };

    BigInt one(1), L2(1), L5(1);

    // 只需处理模 5^k 的情况（v2>=k）
    if (v2 >= k) {
        BigInt M5(1);
        for (int i = 0; i < k; i++) M5 = mulSmall(M5, 5);
        BigInt nmod = mod_from_string(M5);

        // 计算模 5^k 的阶：先用 φ(5^k)=4*5^(k-1) 逐步去因子
        BigInt phi5(1);
        phi5 = mulSmall(phi5, 4);
        for (int i = 1; i < k; i++) phi5 = mulSmall(phi5, 5);
        L5 = phi5;
        // 尝试去掉因子 2
        while (modSmall(L5, 2) == 0) {
            BigInt half = divSmall(L5, 2);
            string exp_str = toString(half);
            BigInt t = pow_mod_str(nmod, exp_str, M5);
            if (cmpBig(t, one) == 0) L5 = half;
            else break;
        }
        // 尝试去掉因子 5
        while (modSmall(L5, 5) == 0) {
            BigInt fifth = divSmall(L5, 5);
            string exp_str = toString(fifth);
            BigInt t = pow_mod_str(nmod, exp_str, M5);
            if (cmpBig(t, one) == 0) L5 = fifth;
            else break;
        }
        cout << toString(L5);
        return 0;
    }

    // 只需处理模 2^k 的情况（v5>=k）
    if (v5 >= k) {
        BigInt M2(1);
        for (int i = 0; i < k; i++) M2 = mulSmall(M2, 2);
        BigInt nmod = mod_from_string(M2);

        BigInt phi2(1);
        for (int i = 0; i < k-1; i++) phi2 = mulSmall(phi2, 2);
        L2 = phi2;
        while (modSmall(L2, 2) == 0) {
            BigInt half = divSmall(L2, 2);
            string exp_str = toString(half);
            BigInt t = pow_mod_str(nmod, exp_str, M2);
            if (cmpBig(t, one) == 0) L2 = half;
            else break;
        }
        cout << toString(L2);
        return 0;
    }

    // v2=v5=0，需同时处理模 2^k 和模 5^k
    {
        BigInt M5(1);
        for (int i = 0; i < k; i++) M5 = mulSmall(M5, 5);
        BigInt nmod = mod_from_string(M5);

        BigInt phi5(1);
        phi5 = mulSmall(phi5, 4);
        for (int i = 1; i < k; i++) phi5 = mulSmall(phi5, 5);
        L5 = phi5;
        while (modSmall(L5, 2) == 0) {
            BigInt half = divSmall(L5, 2);
            string exp_str = toString(half);
            BigInt t = pow_mod_str(nmod, exp_str, M5);
            if (cmpBig(t, one) == 0) L5 = half;
            else break;
        }
        while (modSmall(L5, 5) == 0) {
            BigInt fifth = divSmall(L5, 5);
            string exp_str = toString(fifth);
            BigInt t = pow_mod_str(nmod, exp_str, M5);
            if (cmpBig(t, one) == 0) L5 = fifth;
            else break;
        }
    }
    {
        BigInt M2(1);
        for (int i = 0; i < k; i++) M2 = mulSmall(M2, 2);
        BigInt nmod = mod_from_string(M2);

        BigInt phi2(1);
        for (int i = 0; i < k-1; i++) phi2 = mulSmall(phi2, 2);
        L2 = phi2;
        while (modSmall(L2, 2) == 0) {
            BigInt half = divSmall(L2, 2);
            string exp_str = toString(half);
            BigInt t = pow_mod_str(nmod, exp_str, M2);
            if (cmpBig(t, one) == 0) L2 = half;
            else break;
        }
    }
    // 答案是 L = lcm(L2, L5) = (L2 / gcd(L2,L5)) * L5
    BigInt g = gcdBig(L2, L5);
    BigInt quotient;
    {
        BigInt x = L2, d = g;
        int n = (int)x.a.size();
        int m = (int)d.a.size();
        quotient.a.assign(max(0, n - m + 1), 0);
        BigInt rem; rem.a.clear();
        for (int i = n - 1; i >= 0; --i) {
            rem.a.insert(rem.a.begin(), x.a[i]);
            trim(rem);
            long long low = 0, high = BASE - 1, best = 0;
            while (low <= high) {
                long long mid = (low + high) >> 1;
                BigInt prod = mulSmall(d, mid);
                if (cmpBig(prod, rem) <= 0) { best = mid; low = mid + 1; }
                else { high = mid - 1; }
            }
            if (best) {
                BigInt tmp = mulSmall(d, best);
                rem = subBig(rem, tmp);
            }
            if (i - m + 1 >= 0) quotient.a[i - m + 1] = best;
        }
        trim(quotient);
    }
    BigInt L = mulBig(quotient, L5);
    cout << toString(L);
    return 0;
}