P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version)

· · 题解

题解里头似乎没有离线的做法。实际上，用离线来做，不仅更快，而且更好写。

题意即求

\begin{cases} x-\dfrac yz = n!\\ \dfrac {x-y} z = (n-1)! \\ x\ge 0, z \ge 1 \end{cases}

的 (x, y, z) 数量。

前两式相减，消去 \dfrac y z，得到

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

当 z = 1 时，代入原式发现 n! = (n-1)!，即 n = 1，于是 n = 1 时有无数解。

当 z \gt 1 时，

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

于是 z - 1 是 (n-1)!(n-1) 的因子。由于这个条件是充要的，所以原方程的解数就是右式的因子数。

显然这玩意儿没法直接算。但我们知道，一个数的因子数，就是它唯一分解后质因子指数的任意组合，也即 \prod (\alpha_i+1)。

于是现在的问题，就转化为怎么快速做出 T 个 n 的 (n - 1)!(n-1) 的每个质因子的指数。

对于单个 n，我们可以枚举 i 从 2 到 n - 1，动态维护一个答案 p，表示从 1 到 i - 1 的 \prod (\alpha_i + 1)。显然的，我们分解出 i 后，它对于 p 的贡献是 \dfrac {\alpha'_i+\alpha_i+1}{\alpha'_i+1}（其中 \alpha'_i 表示前 i - 1 个数分解出来的这一位上的指数）。由于是模意义，除法改用逆元。

但本题单单是根号分解就已经过不去了。

可以考虑线性筛筛出每个数的最小质因子，然后从最小质因子开始做分解；于是，复杂度从根号降到对数。

这样，我们就知道了怎么在 O(n\log n) 时间内算出一个 n 的答案。

下面考虑对于 T 个 n，怎么快速进行计算。

非常显然地，对于 n \le m，那么对 n 进行的计算，是被包含在对 m 进行的计算中的。也就是说，如果我们暴力按刚才的方法，以 O(Tn\log n) 时间来算，实际上会进行许多无用功。

于是我们可以考虑离线，然后排序，这样就可以消除无用的计算。维护一个 u 表示下一个要分解的数，于是就可以 n + T\log n 计算出所有询问的答案。

代码实现很简单。

#include <iostream>
#include <algorithm>
#include <bitset>
#define fi first
#define se second
#define int long long
using namespace std;
using pi = pair<int, int>;
const int N = 1e6 + 10, P = 998244353;
int mn[N], primes[N], res[N], s[N], inv[N], nr = 0;
pi z[N];

// 线性筛求最小质因子
void sieve (int n)
{
    for (int i = 2; i <= n; i++) {
        if (!mn[i]) ++nr, mn[primes[nr] = i] = nr;
        for (int j = 1; primes[j] * i <= n; j++) {
            mn[i * primes[j]] = j;
            if (i % primes[j] == 0) break;
        }
    }
}

signed main (void)
{
    int m;

    cin.tie (0)->sync_with_stdio (false);
    // 离线并开筛
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> z[i].fi, --z[i].fi, z[i].se = i;
    sort (z + 1, z + m + 1), sieve (z[m].fi);

    // 线性预处理逆元
    inv[1] = 1;
    for (int i = 2; i <= z[m].fi; i++) inv[i] = (P - P / i) * inv[P % i] % P;

    int i = 1, ans = 1;

    // 特判无解情况
    while (!z[i].fi && i <= m) res[z[i++].se] = -1;
    for (int u = 2; i <= m; i++) {
        // 筛掉 (n - 1)! 中的质因子，并动态维护 ans
        for (; u <= z[i].fi; u++) {
            int v = u;
            while (v > 1) {
                int w = mn[v], cnt = 0;
                while (v % primes[w] == 0) v /= primes[w], cnt++;
                ans = ans * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P, s[w] += cnt;
            }
        }

        // 筛 (n - 1) 项，更新到当前询问的 ans 上
        int prod = ans, val = z[i].fi;
        while (val > 1) {
            int w = mn[val], cnt = 0;
            while (val % primes[w] == 0) val /= primes[w], cnt++;
            prod = prod * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P;
        }
        res[z[i].se] = prod;
    }

    for (int i = 1; i <= m; i++)
        if (res[i] == -1) cout << "inf\n";
        else cout << res[i] << '\n';
    return 0;
}