[语言月赛202302] 最澄澈的空与海 Hard Version 题解

· · 题解

Source & Knowledge

2023 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

多测，T 组数据。每次给定一个正整数 n，求满足 x \geq 0，z \geq 1，x - y \div z = n! 且 (x - y) \div z = \dfrac{n!}{n} 的整数三元组 (x, y, z) 的数量。1 \leq T \leq 10 ^ 5，1 \leq n \leq 10 ^ 6。

解析

本题做法可能有很多种，这里提供一种做法。

以下先给出两个引理，方便解释后面的做法。

引理 1：对于一个满足条件的整数三元组 (x, y, z)，通过 z 可以确定唯一的 x, y 与之对应。

证明：

因为整数三元组 (x, y, z) 满足上述条件，所以 (x - \dfrac yz) - (\dfrac{x - y}{z}) = n! - \dfrac{n!}n，即 x \times \dfrac{z - 1}{z} = (n - 1)! \times (n - 1)。

即 x = (n - 1)! \times (n - 1) \times \dfrac{z}{z - 1}。

显然，接下来 y = x - z \times (n - 1)!。

证毕。

引理 2：在 z \geq 2 的情况下，一个整数三元组 (x, y, z) 满足上述条件的充要条件为 z - 1 是 (n - 1)! \times (n - 1) 的因数。

证明：

由引理 1，当 z \geq 2 时，x = (n - 1)! \times (n - 1) \times \dfrac{z}{z - 1}，y = x - z \times (n - 1)!。此时由于 (n - 1)! > 0，n - 1 \geq 0，z - 1 \geq 1，那么我们就可以保证 x \geq 0。如果此时 x, y 都是整数，那么这个整数三元组就符合题面要求的所有约束。

考虑如何保证 x, y 都是整数。不难发现如果 x 是整数，y 则一定是整数。因此考虑 x 的问题。

注意到导致 x 不是整数的唯一因素是分母 z - 1。因此如果想让 x 是整数，只要保证 (n - 1)! \times (n - 1) \times {z} 可以整除 z - 1 即可。

又 \gcd(z, z - 1) = 1（易证，如果 k 是 z 和 z - 1 的因数，那么 k 就是 z - z + 1 = 1 的因数，所以 k 只能是 1），所以如果 (n - 1)! \times (n - 1) \times {z} 可以整除 z - 1，则只可能为 z - 1 是 (n - 1)! \times (n - 1) 的因数。

对充分性，如果 z - 1 是 (n - 1)! \times (n - 1) 的因数，那么 x = (n - 1)! \times (n - 1) \times \dfrac{z}{z - 1} 就是非负整数，y 同样也是整数。且由引理 1，如果三元组合法，那么当 z 确定时，对应的 x, y 是唯一的。因此一个整数三元组 (x, y, z) 可以满足上述条件。

证毕。

由上面的引理，我们可以发现，对于每个 (n - 1)! \times (n - 1) 的因数 p，我们都可以令 z = p + 1 构造出唯一的整数三元组 (x, y, z) 满足题目给出的条件。同时，由引理 2，可以得出如果 z - 1 不是 (n - 1)! \times (n - 1) 的因数，则一定不能够构造出满足条件的整数三元组。

因此，满足条件的整数三元组的数量，就是 (n - 1)! \times (n - 1) 的因数数量。考虑如何求 (n - 1)! \times (n - 1) 的因数数量。

根据唯一分解定理和约数个数定理，我们可以将问题转化为求解 (n - 1)! \times (n - 1) 的质因数及每个质因数的数量。

首先考虑单组数据的做法。定义一个整数数组 f。其中 f _ i 代表「从 2 开始数的第 i 个质数」作为质因数在 (n - 1)! \times (n - 1) 中出现的次数。将 i 从 1 枚举至 n - 1，对于每一个 i，将其进行质因数分解。设分解后的结果为 i = p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}，对每个 p _ j，让 f 中对应的位置增加 e _ j。最后将 n - 1 单独多进行一次这个过程。

上述过程完成后，设 \leq n 的质数为 cnt 个，我们计算出 (1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt}) 取模即可作为答案。

对于上述的整套流程，时间上的瓶颈在质因数分解部分。考虑优化质因数分解过程。

考虑线性筛质数的原理。线性筛质数过程中，每个合数都只被标记一次。在这唯一一次标记的过程中，这个合数是被其最小的质因数标记的。在标记的同时，我们考虑记录下这个最小的质因数。

我们使用 p 数组记录线性筛质数过程，p _ i 代表 i 的最小的质因数。这样做的好处是，在进行质因数分解的过程中，我们可以直接找到对应整数的最小质因数直接进行分拆，而不需要从头遍历质数表逐一匹配。不难发现，我们可以在 \mathcal{O} (\log n) 的时间复杂度内完成对 n 的质因数分解。

我们首先进行一次线性筛质数，同时记录下 p 数组。线性筛完成后，进行「将 i 从 1 枚举至 n - 1，对于每一个 i，将其进行质因数分解」的过程。这样对于单次询问，最终的总时间复杂度为 \mathcal{O} (n \log n)。

然而多测的总时间复杂度为 \mathcal{O} (Tn \log n)，按照上述方法只能拿到 60\% 的分数。考虑如何优化的多测的过程。

不难发现我们对 (n - 1)! 的质因数及个数进行了多次重复的运算，这是非常耗时的！考虑如何优化这个过程。

如果只是询问 (n - 1)! 的因数数量，我们显然可以进行递推。使用 h 数组记录答案，将 i 从 1 枚举至 n - 1，对于每一个 i，将其进行质因数分解，每次分解并操作完 f 数组后，计算 (1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt}) 并取模存入 h _ i 中即可。瓶颈转化为了计算 (1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})。

考虑使用一个变量 ans 记录当前的 (1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})。在对 i 筛质因数的过程中，我们每筛出一个质因数及对应的数量（设这个质因数为第 x 个质数，出现 y 次），就将 ans 先除以 1 + f _ {x}，再乘 1 + f _ {x} + y，再让 f _ x 增加 y。最后将 ans 存入 h _ i 即可。

由于 ans 需要取模，因此上述的除法转换为乘逆元即可。这样，如果使用线性预处理逆元，我们即可在 \mathcal{O} (\log n) 的时间内完成对 n 的质因数分解和答案 ans 的更新。最终便可 \mathcal{O} (n \log n) 预处理，\mathcal{O}(1) 回答。实际上不使用线性求逆元也可以在时限一半以内通过本题。

但是本题在 (n - 1)! 外还有一个 (n - 1)，考虑处理这个 (n - 1)。我们在上面的过程中提到了增添一个 (n - 1) 对答案的处理（将 ans 先除后乘，修改 f 数组，将 ans 存入 h 答案数组），这里，我们考虑对单独的 (n - 1) 先增添后撤销。具体的，设 n - 1 的某个质因数为第 x 个质数，出现 y 次，先「对所有的质因数，将 ans 先除以 1 + f _ {x}，再乘 1 + f _ {x} + y，再让 f _ x 增加 y。最后将 ans 存入 h _ i」，答案记录完成后再「对所有的质因数，将 ans 先除以 1 + f _ x，再乘 1 + f _ {x} - y，让 f _ x 减少 y。不将 ans 存入 h _ i」即可。

这样我们即可在 \mathcal{O}(n \log n) 的时间内完成所有的预处理工作，之后 \mathcal{O} (1) 回答即可。总时间复杂度 \mathcal{O}(n \log n + T)。

最后有一个特殊情况需要处理。对于引理 2，我们只证明了 z \geq 2 的情况。为什么没有证明 z = 1 呢？显然是因为此时分母是 z - 1= 0。

那如果我非要让 z = 1 呢？令 z = 1，我们会得到这样的一组式子：

\begin{cases} x - y = n! \\ x - y = (n - 1)! \end{cases}

会得到 n! = (n - 1)!，这个式子成立当且仅当 n = 1。此时 n! = (n - 1)! = 1。

所以，当 n = 1 时，我们让 z = 1，只需让 x - y = 1，三元组 (x, y, z) 就是符合要求的。显然这样的三元组有无数个。

所以当且仅当 n = 1，输出一行 inf。

代码

标答代码写的很丑陋（诸如没有采用线性求逆元），洛谷上开启 O2 后单个点在 700ms 左右通过，所以考虑后时限设置为两秒。

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

#define lint long long
#define rep(_, __, ___) for (int _ = __; _ <= ___; ++_)

const int maxn = 1e6 + 5;
const int modint = 998244353;
using pii = pair<int, int>;

namespace FactorSieve {

    int prime[maxn];
    int ans[maxn];
    int p[maxn];
    int cnt;
    int f[maxn];

    lint fpow(lint x, lint y) {
        lint ans = 1;
        while (y) {
            if (y & 1) {
                ans = (ans * x) % modint;
            }
            x = (x * x) % modint;
            y >>= 1;
        }
        return ans;
    }

    lint finv(lint x) {
        return fpow(x, modint - 2);
    }

    pii v[maxn];
    int vcnt = 0;

    void init() {
        for (int i = 2; i <= 1000000; i++) {
            if (!p[i]) {
                p[i] = i, prime[++cnt] = i;
            }
            for (int j = 1; j <= cnt && i * prime[j] <= 1000000; j++) {
                p[i * prime[j]] = prime[j];
                if (p[i] == prime[j])
                    break;
            }
        }

        lint cur = ans[0] = 1;

        for (int i = 1; i <= 1000000; ++i) {
            vcnt = 0;
            lint var = i;
            while (var != 1) {
                int cnt = 0, cur = p[var];
                while (var % cur == 0)
                    var /= cur, ++cnt;
                v[++vcnt] = make_pair(cur, cnt);
            }
            for (int k = 1; k <= vcnt; ++k) {
                pii j = v[k];
                cur *= finv(1 + f[j.first]);
                cur %= modint;
                f[j.first] += j.second * 2;
                cur *= 1 + f[j.first];
                cur %= modint;
            }
            ans[i] = cur;
            for (int k = 1; k <= vcnt; ++k) {
                pii j = v[k];
                cur *= finv(1 + f[j.first]);
                cur %= modint;
                f[j.first] -= j.second;
                cur *= 1 + f[j.first];
                cur %= modint;
            }
        }
    }

    int query(int x) {
        return ans[x];
    }
};

int main() {
    FactorSieve::init();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 1)
            printf("inf\n");
        else
            printf("%d\n", FactorSieve::query(n - 1));
    }
    return 0;
}