Big Integer - 题解

标签与难度

标签: 数论, 模运算, 费马小定理, 乘法阶, 素数筛, 质因数分解 难度: 1900

题目大意喵~

主人你好呀，喵~ 这道题是关于一种特殊的“大整数”的！

我们定义一种只由数字 1 构成的数，记作 $A(k)$，它表示由 $k$ 个 1 组成的整数。比如，$A(1)=1$, $A(2)=11$, $A(3)=111$ 这样子，是不是很可爱捏？

题目要求我们，对于给定的素数 $p$ 和两个正整数 $n, m$，找出有多少对 $(i, j)$ 满足下面这些条件：

1. $1 \le i \le n$
2. $1 \le j \le m$
3. $A(i^j)$ 能够被 $p$ 整除，也就是 $A(i^j) \equiv 0 \pmod p$。

我们要做的就是数出所有这样符合条件的 $(i, j)$ 对的数量，然后告诉裁判，喵~

解题思路分析

这道题看起来像是在和巨大的数字玩耍，但其实是数论里的小魔法哦！让我一步步带你解开谜题吧，喵~

第一步：把 $A(k)$ 变成我们熟悉的公式

首先，$A(k)$ 这个全是 1 的数字，我们可以把它写成一个等比数列求和的形式，呐： $A(k) = 1 + 10 + 10^2 + \dots + 10^{k-1} = \frac{10^k - 1}{10 - 1} = \frac{10^k - 1}{9}$

所以，题目中的条件 $A(i^j) \equiv 0 \pmod p$ 就变成了：

$$\frac{10^{i^j} - 1}{9} \equiv 0 \pmod p$$

第二步：处理讨厌的除法和特殊情况

这个分母 9 有点碍眼，我们得想办法处理掉它。这就要分类讨论啦！

特殊情况 1: $p=2$ 或 $p=5$

• 如果 $p=2$ 或者 $p=5$，它们是 $10$ 的因子。
• $A(k)$ 的个位数永远是 1，所以它不可能是偶数，也就不可能被 $2$ 整除。
• $A(k) \pmod 5$ 呢？$10^k - 1$ 的个位数总是 9，所以 $10^k-1 \equiv 4 \pmod 5$。而分母 $9 \equiv 4 \pmod 5$。所以 $A(k) \equiv 4 \cdot 4^{-1} \equiv 1 \pmod 5$。它也永远不会被 $5$ 整除。
• 所以，当 $p=2$ 或 $p=5$ 时，没有任何 $(i, j)$ 满足条件，答案就是 0，喵~

特殊情况 2: $p=3$

• 当 $p=3$ 时，我们不能直接在模 $p$ 的意义下两边乘以 $9$（因为 $9 \equiv 0 \pmod 3$）。
• 但是有一个判断整除 3 的小技巧：一个数能被 3 整除，当且仅当它的各位数字之和能被 3 整除。
• $A(k)$ 的各位数字之和就是 $k$ 个 1 相加，结果是 $k$。
• 所以，$A(k) \equiv 0 \pmod 3 \iff k \equiv 0 \pmod 3$。
• 我们的条件就变成了 $i^j$ 是 $3$ 的倍数。这只要 $i$ 本身是 $3$ 的倍数就可以啦！
• 所以我们只需要数出在 $[1, n]$ 中有多少个 $3$ 的倍数，也就是 $\lfloor n/3 \rfloor$ 个。对于每个这样的 $i$，$j$ 可以取 $[1, m]$ 中的任意值。
• 所以答案是 $\lfloor n/3 \rfloor \times m$。

一般情况: $p \neq 2, 3, 5$

• 在这种情况下，$p$ 和 $9$ 是互质的，我们可以放心地在同余式两边乘以 $9$ 的逆元，或者直接乘以 $9$，得到：

  $$10^{i^j} - 1 \equiv 0 \pmod p \implies 10^{i^j} \equiv 1 \pmod p$$

• 这下问题就清晰多啦！我们现在需要解决的是 $10$ 在模 $p$ 意义下的幂次问题。

第三步：引入“乘法阶”这个神奇道具！

看到 $a^k \equiv 1 \pmod p$ 这种形式，就要立刻想到一个数论中的强大工具——乘法阶！

一个数 $a$ 模 $p$ 的乘法阶，记作 $\text{ord}_p(a)$，是使得 $a^k \equiv 1 \pmod p$ 成立的最小正整数 $k$。

它有一个非常重要的性质：$a^x \equiv 1 \pmod p \iff x \equiv 0 \pmod{\text{ord}_p(a)}$。

所以，我们的条件 $10^{i^j} \equiv 1 \pmod p$ 就等价于：

$$i^j \text{ 是 } \text{ord}_p(10) \text{ 的倍数}$$

我们把这个最小的周期 $d = \text{ord}_p(10)$ 求出来，问题就变成了：数出有多少对 $(i,j)$ 满足 $d \mid i^j$。

怎么求 $d = \text{ord}_p(10)$ 呢？ 根据费马小定理，$10^{p-1} \equiv 1 \pmod p$。这意味着 $d$ 一定是 $p-1$ 的一个因子。所以我们不需要从 $1$ 开始傻傻地试，只需要遍历 $p-1$ 的所有因子，从小到大测试，第一个满足 $10^k \equiv 1 \pmod p$ 的就是我们的 $d$ 啦！

第四步：终极计数！

现在我们的目标是：计数满足 $d \mid i^j$ 的 $(i, j)$ 对。

这个问题直接数不好数，我们可以换个角度：固定 $j$，然后数有多少个符合条件的 $i$。

让我们对 $d$ 进行质因数分解：$d = q_1^{c_1} q_2^{c_2} \cdots q_k^{c_k}$。 同样对 $i$ 进行质因数分解：$i = q_1^{a_1} q_2^{a_2} \cdots q_k^{a_k} \cdots$。 那么 $i^j = q_1^{j \cdot a_1} q_2^{j \cdot a_2} \cdots q_k^{j \cdot a_k} \cdots$。

要让 $d \mid i^j$，就必须保证对于 $d$ 的每一个质因子 $q_r$，它在 $i^j$ 中的幂次 $j \cdot a_r$ 不小于它在 $d$ 中的幂次 $c_r$。也就是：

$$j \cdot a_r \ge c_r \quad \text{对于所有 } r=1, \dots, k$$

$$\implies a_r \ge \frac{c_r}{j}$$

因为 $a_r$ 是整数，所以 $a_r \ge \lceil \frac{c_r}{j} \rceil$。这里的 $\lceil x \rceil$ 是向上取整哦。

这意味着，对于一个固定的 $j$， $i$ 必须是 $\prod_{r=1}^{k} q_r^{\lceil c_r/j \rceil}$ 的倍数。我们把这个数记作 $S_j$。 那么，对于固定的 $j$，在 $[1, n]$ 范围内满足条件的 $i$ 的数量就是 $\lfloor n/S_j \rfloor$。

所以总答案就是：

$$\text{Ans} = \sum_{j=1}^{m} \lfloor n/S_j \rfloor$$

第五步：一个重要的优化

如果 $m$ 非常大，一个一个地计算 $S_j$ 再求和会超时。我的猫爪可受不了这么大的计算量！

我们来观察 $S_j = \prod_{r=1}^{k} q_r^{\lceil c_r/j \rceil}$。 当 $j$ 逐渐增大时，$\lceil c_r/j \rceil$ 是不会增大的。所以 $S_j$ 是一个非递增的序列。 更重要的是，当 $j$ 变得足够大（具体来说，当 $j > \max\{c_1, c_2, \dots, c_k\}$ 时），所有的 $\lceil c_r/j \rceil$ 都会变成 $1$。 这时，$S_j$ 会稳定下来，变成一个常数 $S_{\text{stable}} = \prod_{r=1}^{k} q_r^1 = \text{rad}(d)$（$d$ 的质因数之积）。 $d < p \le 10^9+7$，那么 $d$ 的质因数分解中，指数 $c_r$ 不会太大（比如 $2^{30} > 10^9$），所以 $j$ 很快就会超过所有的 $c_r$。经验上这个阈值大概在 30 到 60 之间。

所以我们的策略是：

1. 从小到大遍历 $j$。
2. 计算 $S_j$ 和 $\lfloor n/S_j \rfloor$ 并累加到答案中。
3. 检查是否所有的 $\lceil c_r/j \rceil$ 都等于 $1$ 了。
4. 如果都等于 $1$ 了，说明从当前 $j$ 到 $m$，所有的 $S_j$ 值都一样。我们就可以直接把剩下的 $(m-j+1)$ 项一次性算出来，然后潇洒地 break 掉循环！

这样，我们就把一个可能很长的循环变成了一个很短的循环，完美解决问题，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 注释超详细的，快来看看吧！

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 使用 long long 防止整数溢出
using ll = long long;

// 快速幂函数，用于计算 (base^exp) % mod
ll power(ll base, ll exp, ll mod) {
    ll 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;
}

// 普通的整数幂函数，计算 base^exp
ll integer_power(ll base, int exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res *= base;
        base *= base;
        exp /= 2;
    }
    return res;
}

// 获取d的质因数分解
std::vector<std::pair<ll, int>> get_prime_factors(ll d) {
    std::vector<std::pair<ll, int>> factors;
    for (ll i = 2; i * i <= d; ++i) {
        if (d % i == 0) {
            int count = 0;
            while (d % i == 0) {
                d /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    if (d > 1) {
        factors.push_back({d, 1});
    }
    return factors;
}


void solve() {
    ll p, n, m;
    std::cin >> p >> n >> m;

    // 特殊情况 1: p=2 或 p=5，A(k)永远无法被它们整除
    if (p == 2 || p == 5) {
        std::cout << 0 << std::endl;
        return;
    }
    // 特殊情况 2: p=3, A(k)能被3整除 <=> k能被3整除
    if (p == 3) {
        std::cout << (n / 3) * m << std::endl;
        return;
    }

    // --- 一般情况 ---
    // 1. 找到 10 模 p 的乘法阶 d
    ll phi = p - 1;
    ll order_d = phi;
    std::vector<ll> divisors;
    for (ll i = 1; i * i <= phi; ++i) {
        if (phi % i == 0) {
            divisors.push_back(i);
            if (i * i != phi) {
                divisors.push_back(phi / i);
            }
        }
    }
    std::sort(divisors.begin(), divisors.end());

    for (ll div : divisors) {
        if (power(10, div, p) == 1) {
            order_d = div;
            break;
        }
    }

    // 2. 对 d 进行质因数分解
    auto prime_factors_of_d = get_prime_factors(order_d);
    
    // 3. 迭代 j，计算答案
    ll ans = 0;
    for (ll j = 1; j <= m; ++j) {
        ll required_multiple_Sj = 1;
        bool is_stable = true;

        for (const auto& factor : prime_factors_of_d) {
            ll prime = factor.first;
            int exponent_in_d = factor.second;
            
            // 计算 ceil(c/j)，即 (c + j - 1) / j
            int required_exponent = (exponent_in_d + j - 1) / j;
            
            if (required_exponent > 1) {
                is_stable = false;
            }
            
            // 计算 p_r ^ ceil(c_r/j)
            required_multiple_Sj *= integer_power(prime, required_exponent);
        }
        
        ans += n / required_multiple_Sj;

        // 优化：如果S_j已经稳定，一次性计算剩余部分
        if (is_stable) {
            ans += (n / required_multiple_Sj) * (m - j);
            break;
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(T \cdot (\sqrt{p} \log p))$，其中 $T$ 是测试用例的数量。

  • 对于每个测试用例，最耗时的部分是找到乘法阶 $d$。我们需要遍历 $p-1$ 的所有因子，这需要 $O(\sqrt{p-1})$ 的时间。对于每个因子，我们都要做一次快速幂，其复杂度为 $O(\log p)$。
  • 质因数分解 $d$ 的复杂度是 $O(\sqrt{d})$，因为 $d < p$，所以这部分不会超过 $O(\sqrt{p})$。
  • 最后计算答案的循环，由于优化，只会执行很少的次数（大约是 $\log d$ 的级别，通常是几十次），所以这部分的时间可以忽略不计。
  • 因此，总的时间复杂度由求乘法阶的部分主导，为 $O(\sqrt{p} \log p)$。

• 空间复杂度: $O(\sqrt{p})$。

  • 主要的空间开销来自于存储 $p-1$ 的所有因子，最坏情况下因子数量级是 $O(\sqrt{p})$。
  • 存储 $d$ 的质因子所用的空间非常小，可以忽略。

知识点总结

这道题是数论知识的绝佳练习场，喵~

1. 等比数列求和: 将特殊形式的数 $A(k)$ 转化为数学公式 $\frac{10^k-1}{9}$ 是解题的第一步。
2. 模运算与分类讨论: 处理分母时，需要根据模数 $p$ 是否与分母互质进行分类讨论，这是数论题中的常见技巧。
3. 乘法阶 (Multiplicative Order): 核心概念！理解 $a^x \equiv 1 \pmod p \iff \text{ord}_p(a) \mid x$ 是解决问题的关键。
4. 费马小定理: 它是找到乘法阶的理论基础，告诉我们阶一定是 $p-1$ 的因子，大大缩小了搜索范围。
5. 质因数分解: 将整除问题 $d \mid i^j$ 转化为对每个质因子的幂次进行比较，是处理整除问题的标准方法。
6. 循环优化: 对于求和式 $\sum_{j=1}^{m} f(j)$，如果发现 $f(j)$ 在 $j$ 超过某个阈值后变为常数，就可以进行优化，将 $O(m)$ 的循环降到 $O(\text{threshold})$。

希望这篇题解能帮到你，主人！如果还有问题，随时可以再来问我哦，喵~