专栏文章

P1050题解

MMasterArcherSkeleton
P1050题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqhjnb5
此快照首次捕获于
2025/12/04 04:54
3 个月前
此快照最后确认于
2025/12/04 04:54
3 个月前
查看原文

提前说的话

本文中：
所有 ∣\mid 符号（a∣ba \mid b）表示 aa 整除 bb（即：存在一个 c∈Zc \in \Z，使 b=acb = ac）；
所有提到“位”（进制位）的地方都指十进制下的进制位。而位的编号从右往左依次 11、22、33、……，后 xx 位表示编号为 11 ~ xx 的进制位，第 xx 位表示编号为 xx 的进制位；

题意简化

问：nn 的正整数次幂（在十进制下）的最后 kk 位的循环长度。如果循环不存在，输出 −1-1。
形式化的讲：给定 n,k∈N∗n,k \in \N^*，求最小的 L∈N∗L \in \N^*，使对于任意的 a∈N∗a \in \N^*，都有 na≡na+L(mod10k)n^a \equiv n^{a+L} \pmod {10^k}。若不存在，则输出 −1-1。如果想看题目的话，就点击右边：P1050 [NOIP2005 普及组] 循环。

暴力（30pts）

根据同余（取模）的性质，有：
((x mod p)⋅(y mod p))≡(x⋅y)(modp)(*)\tag{*} ((x \bmod p) \cdot (y \bmod p)) \equiv (x \cdot y) \pmod {p}
将 x=nm(m∈N)x = n^m(m \in \N)，y=ny = n，p=10kp = 10^k 代入(∗)(*) 式，得：((nm mod 10k)⋅(n mod 10k))≡nm⋅n(mod10k)((n^m \bmod 10^k) \cdot (n \bmod 10^k)) \equiv n^m \cdot n \pmod {10^k}。所以，已知 nm mod 10kn^m \bmod 10^k，乘上 nn（这里也可以提前将 nn 对 10k10^k 取模，可以利用 (∗)(*) 式在刚开始就一边一位一位地输入一边对 10k10^k 取模）后再对 10k10^k 取模，即可得到 nm+1 mod 10kn^{m+1} \bmod 10^k。
所以，让 ii 从 11 到一个很大的数循环，当第一次出现满足 ni+1≡n(mod10k)n^{i + 1} \equiv n \pmod {10^k} 的 ii 时，答案 LL 就是 ii，可以直接输出并结束运行。问题就是：如何判断无解呢？因为总共有 10k10^k 种模 10k10^k 的结果，所以考虑最极端的情况，前 10k−110^k - 1 个 ii（即：i≤10k−1i \le 10^k - 1）时，都有 ni+1 ≡/  n(mod10k)n^{i+1} \text{ } {\equiv}\mathllap{/\,} \text{ } n \pmod {10^k}。则若存在循环，必有 n10k+1≡n(mod10k)n^{10^k + 1} \equiv n \pmod {10^k}，即：在上面最极端的情况成立的情况下需要存在循环，在 i=10ki = 10^k 时，必有 ni+1≡n(mod10k)n^{i+1} \equiv n \pmod {10^k}。即：最多只需要循环 10k10^k 次，仍然没有结束运行的话，就是无解，输出 −1-1。
这里给出一个代码片段：
CPP
while(k--) m *= 10;
n %= m;
s = n;
for(int i = 1; i <= m; i ++) {
    s = s * n % m;
    if(s == n) {
        cout << i;
        return 0;
    }
}
cout << -1;
return 0;
当然，这样只有 30pts。

正解（递推法）

令 li(i∈N)l_i(i \in \N) 表示后 ii 位的 最小 循环长度（设 l0=1l_0 = 1，若后 ii 位不存在循环，则令 li=0l_i = 0（方便日后计算、描述））。
问：若现已知 li−1(i∈N∗)l_{i-1}(i \in \N^*)，是否能够求出 lil_i？
引理 1：若 li≠0(i∈N∗)l_i \ne 0(i \in \N^*)，则必有 li−1∣lil_{i - 1} \mid l_i。
证明：
因为 li≠0l_i \ne 0，所以存在后 ii 位长度为 lil_i 的长度最小循环。因此，后 i−1i - 1 位也存在一个长度为 lil_i 的循环（不一定是最小），即：后 i−1i - 1 位存在循环，即：li−1≠0l_{i - 1} \ne 0。
又因为后 i−1i - 1 存在长度为 li−1l_{i - 1} 的长度最小循环，而后 i−1i - 1 位的所有循环长度必定是 li−1l_{i - 1} 的正整数倍，且后 i−1i - 1 位存在一个长度为 lil_i 的循环。所以 li−1∣lil_{i - 1} \mid l_i。
既然有了引理 1，我们就会想：当 i∈N∗i \in \N^*，li≠0l_i \ne 0 时，lil_i 是 li−1l_{i - 1} 的多少倍呢？
令 f(i)(i∈N∗)f(i)(i \in \N^*)，满足 li−1⋅f(i)=lil_{i - 1} \cdot f(i) = l_i（由引理 1，当 li≠0l_i \ne 0 时，f(i)=lili−1f(i) = \frac{l_i}{l_{i - 1}}；而当 li=0l_i = 0 时，f(i)=0f(i) = 0（这一点更重要）。而 f(i)f(i) 是一定唯一的），则有 ∀i∈N∗\forall i \in \N^*，f(i)∈N∗f(i) \in \N^*。所以，只要能够求出 f(i)f(i)，就能够求出 lil_i 了。
那么，如何求出 f(i)f(i) 呢？当然 f(i)f(i) 可能为 00，此时代表无解。能否暴力枚举呢？那我们需要一个界限，我们来计算一下 f(i)f(i) 的最大值是多少。
注意到，在考虑后 ii 位时，长为 lil_i 的循环节中的后 li−1l_{i-1} 位将长为 li−1l_{i-1} 的循环节重复 f(i)f(i)。所以，要确定 f(i)f(i) 的上界，第 ii 位肯定是关键。即：当出现第一个（最小的）j(j∈N∗)j(j \in \N^*)，使 nj⋅li−1+1n^{j \cdot l_{i - 1} + 1} 的第 ii 位与 nn 的第 ii 位相等时，f(i)=jf(i) = j。要求 f(i)f(i) 的上限，即求 li>0l_i > 0 时，jj 的最大值。
同【暴力】，因为一位上一共只有 00 ~ 99 十种可能，所以考虑最极端的情况。前 99 个 jj（j≤9j \le 9）时，都有：nj⋅li−1+1n^{j \cdot l_{i - 1} + 1} 的第 ii 位与 nn 的第 ii 位不相等。则若 li≠0l_i \ne 0，当 j=10j = 10 时，必有：nj⋅li−1+1n^{j \cdot l_{i - 1} + 1} 的第 ii 位与 nn 的第 ii 位相等。即：li>0l_i > 0 时，jj 的最大值为 1010。即：f(i)f(i) 的最大值为 1010。
所以，枚举 f(i)f(i)，从 11 到 1010，判断是否满足 nj⋅li−1+1n^{j \cdot l_{i - 1} + 1} 的第 ii 位与 nn 的第 ii 位相等。若相等，则退出循环；若直至循环结束都没有一个在枚举范围内的满足条件的 f(i)f(i)，则 f(i)=0f(i) = 0。
而 li=(∏j=1if(j))⋅l0=∏j=1if(j)l_i = (\prod_{j=1}^{i} f(j)) \cdot l_0 = \prod_{j=1}^{i} f(j)，所以此时将 i=ki = k 代入这个式子，就可以求出所求的 lkl_k 了。
当 lk=0l_k = 0 时，就输出 −1-1，否则输出 lkl_k。
当然，lk=0l_k = 0 当且仅当存在一个 i∈N∗i \in \N^*，且 1≤i≤k1 \le i \le k，满足 f(i)=0f(i) = 0 时才成立。所以，如果在计算时已经遇到了 f(i)=0f(i) = 0 的情况，可以直接输出 −1-1 并结束运行，如果计算完后，程序仍没有结束运行，则输出 ∏i=1kf(i)\prod_{i=1}^{k} f(i)（可以在循环中进行求和）。
不过，上面的思路还是比较“粗”，就是没有明确如何去细化、实现，只能说是一个大纲吧，有很多地方都还没有细化。所以，接下来就细化上面的思路。关于中间求 nj⋅li−1+1(j∈N∗,j≤10)n^{j \cdot l_{i - 1} + 1}(j \in \N^*,j \le 10) 的第 kk 位的部分，肯定是不能直接求的。然而，我们注意到，这里的 jj 是从 11 到 1010 进行枚举的，即：jj 是递增的。所以，就可以根据前一个 jj 时的情况来推出现在的 jj 时的情况。根据同余（取模）的性质，nj⋅li−1+1≡(n(j−1)⋅li−1+1 mod 10i)⋅(nli−1 mod 10i)(mod10i)n^{j \cdot l_{i - 1} + 1} \equiv (n^{(j - 1) \cdot l_{i - 1} + 1} \bmod 10^i) \cdot (n^{l_{i-1}} \bmod 10^i) \pmod {10^i}。所以，可以每次求出 nli−1 mod 10in^{l_{i-1}} \bmod 10^i，并在枚举 jj 时计算即可。然而，这样做并不是最优的，可以进一步优化。注意到，在递推求解的时候，外层的 ii 是从 11 到 kk 进行递推的，也就是说，ii 跟 jj 一样，都是递增的。所以，可以用类似于 jj 的方法，保留上次的 ff 函数结果，因为 nj⋅li−1+1=nj⋅li−2⋅f(i−1)+1=n⋅((nli−2)f(i−1))jn^{j \cdot l_{i - 1} + 1} = n^{j \cdot l_{i - 2} \cdot f(i - 1) + 1} = n \cdot ((n^{l_{i - 2}})^{f(i - 1)})^j（可以令 f(0)=l−1=1f(0) = l_{-1} = 1）。所以，可以在开始内层循环之前就预处理出 (nli−2)f(i−1)(n^{l_{i - 2}})^{f(i - 1)}，在内层循环（枚举 jj）里就不断地去乘它就可以了。但是，注意到前文说要对 10i10^i 取模，那么模数就不能通用了。所以，我们对 10k10^k 取模（因为 i≤ki \le k）即可。
但是，这道题的数据范围很惊人，达到了 n≤10100n \le 10^{100}，这就意味着，我们必须要用高精度了。那么，在运行过程中，要用到哪些运算呢？可以发现，只有两种：高精乘高精和高精乘低精（都要取模）。那么，在写高精度的时候，就需要写这两种运算了。
好了，来估计一下时间复杂度。外层 ii 从 11 到 kk，内层先是 f(i−1)f(i - 1) 次高精乘高精，再是最大 1010 次的高精乘高精以及判断，又是一个特判，最后是一次高精乘低精。而一次高精乘高精的时间复杂度是 O(k2)\Omicron(k^2)，一次高精乘低精的时间复杂度是 O(k)\Omicron(k)，f(i−1)≤10f(i - 1) \le 10，所以整体的时间复杂度大约就是 O(10k3)\Omicron(10 k^3)，能过了。

代码实现

上面就是思路了，下面上代码。
CPP
#include <bits/stdc++.h>
using namespace std;
int k, f[110];
struct Number {
    int l, a[210];
    void Clear() {
        l = 0;
        memset(a, 0, sizeof(a));
    }
    void Resize() {
        if(l > k) l = k;
    }
    void In() {
        string str;
        cin >> str;
        Clear();
        for(int i = str.size() - 1; i >= 0; i --) {
            a[++l] = (str[i] - '0');
        }
    }
    void Out() {
        for(int i = l; i >= 1; i --) {
            cout << a[i];
        }
    }
    void InInt(int x) {
        Clear();
        while(x) {
            a[++l] = x % 10;
            x /= 10;
        }
        Resize();
    }
}n, u, v, w, ans;
Number operator * (Number p, Number q) {
    Number rhs;
    rhs.Clear();
    for(int i = 1; i <= p.l; i ++) {
        for(int j = 1; j <= q.l; j ++) {
            rhs.a[i + j - 1] += (p.a[i] * q.a[j]);
            rhs.a[i + j] += (rhs.a[i + j - 1] / 10);
            rhs.a[i + j - 1] %= 10;
        }
    }
    if(rhs.a[p.l + q.l]) rhs.l = p.l + q.l;
    else rhs.l = p.l + q.l - 1;
    rhs.Resize();
    return rhs;
}
int main() {
    n.In();
    cin >> k;
    n.Resize();
    f[0] = 1;
    v = n;
    ans.InInt(1);
    for(int i = 1; i <= k; i ++) {
        u.InInt(1);
        for(int j = 1; j <= f[i - 1]; j ++) {
            u = u * v;
        }
        v = u;
        w = n;
        for(int j = 1; j <= 10; j ++) {
            w = w * u;
            if(w.a[i] == n.a[i]) {
                f[i] = j;
                break;
            }
        }
        if(!f[i]) {
            cout << -1;
            return 0;
        }
        w.InInt(f[i]);
        ans = ans * w;
    }
    ans.Out();
    return 0;
}
代码仅供参考，不喜勿喷。

数据通过情况

数据通过情况

最后的话

这道题主要考到了：递推和高精度。关于代码，还是自己写，不要抄！最后的最后，写篇文章不容易，可否来个赞？

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...