题目理解

我们定义一个长度为 $n$ 的数组 $a$ 是“好的”，当且仅当对于所有 $1 \le i < j \le n$，都有 $f(i) \neq f(j)$。

其中 $f(k) = \gcd(\max(a[l..l+k-1]) \mid 1 \le l \le n-k+1)$，即所有长度为 $k$ 的子数组的最大值的 GCD。

题目要求：统计所有非空好数组的数量，数组元素在 $[1, m]$ 范围内，答案对 $998244353$ 取模。

关键观察

观察$1$：$f(k)$ 的单调性

可以证明 $f(k)$ 是单调非增的。更具体地说：

• $f(1) = \gcd(a_1, a_2, ..., a_n)$，即整个数组的 GCD
• 随着 $k$ 增大，$f(k)$ 要么保持不变，要么变小

观察$2$：好数组的条件

由于 $f(k)$ 是单调的，且要求所有 $f(k)$ 互不相同，这意味着：

$$f(1) > f(2) > f(3) > ... > f(n) > 0$$

即 $f(k)$ 必须严格递减。

观察$3$：$f(k)$ 与数组结构的关系

对于好数组，我们可以证明每个 $f(k)$ 必须是某个前缀 $GCD$ 的倍数。更关键的是，存在一个与数组等价的表示：

设 $g_i$ 表示从位置 $i$ 开始的后缀 $GCD$（即 $\gcd(a_i, a_{i+1}, ..., a_n)$），那么：

• $g_1 = f(1)$
• $g_n = a_n$
• $g_i$ 是单调递减的（不严格）
• 相邻的 $g$ 值要么相等，要么除以某个因子

动态规划思路

状态定义

设 $dp_{j,h}$ 表示：当前处理到位置 $j$，且从位置 $j$ 开始的后缀 $GCD$ 为 $h$ 时，所有可能的数组的贡献和。

这里“贡献”指的是 $2^{\text{已构建长度}-1}$ 的累加。

转移方程

当我们从位置 $i$ 转移到位置 $j$（$j > i$）时，需要满足： $1$. $h \mid g$（其中 $g$ 是位置 $i$ 的后缀 GCD） $2$. $g < h$（保证严格递减） $3$. $g = \gcd(j, h)$（这是由后缀 GCD 的性质决定的）

因此转移为：

$$dp_{j,h} = \sum_{g \mid h, g < h, g = \gcd(j, h)} dp_{i,g} $$

优化

直接枚举 $i$ 和 $g$ 的复杂度太高。注意到：

• 条件 $g = \gcd(j, h)$ 意味着 $g$ 由 $j$ 和 $h$ 唯一确定
• 我们实际上只需要知道所有 $i$ 的累加和

定义 $S_{j,h} = \sum_{i < j} dp_{i,\gcd(j,h)}$，但这样仍然复杂。

更好的做法：使用莫比乌斯反演或 $SOS$ $DP$ 来加速。

最终算法

预处理

$1$. 使用线性筛预处理每个数的最小质因子 $2$. 计算莫比乌斯函数 $\mu(n)$ $3$. 预计算 $2^k \mod MOD$

核心公式

经过推导，对于固定的 $m$，答案为：

$$ans(m) = \sum_{i=1}^m \sum_{d|i} \mu(d) \cdot 2^{\frac{i}{d}-1} $$

或者等价地：

$$ans(m) = \sum_{k=1}^m 2^{k-1} \cdot \left(\sum_{d=1}^{\lfloor m/k \rfloor} \mu(d)\right) $$

但更高效的实现是直接使用容斥：

$$dp[i] = \sum_{j|i} \mu(j) \cdot 2^{\frac{i}{j}-1}$$

然后 $ans(m) = \sum_{i=1}^m dp[i]$。

时间复杂度

$O(M \log M)$ 预处理，$O(1)$ 回答每个查询，其中 $M = \max(m)$。

完整代码

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

const int MOD = 998244353;
const int MAXM = 1e6 + 5;

void solve() {
    int t;
    cin >> t;
    
    vector<int> queries(t);
    int max_m = 0;
    for (int i = 0; i < t; i++) {
        cin >> queries[i];
        max_m = max(max_m, queries[i]);
    }
    
    // 预处理最小质因子和莫比乌斯函数
    vector<int> mu(max_m + 1, 1);
    vector<int> min_prime(max_m + 1, 0);
    
    for (int i = 2; i <= max_m; i++) {
        if (min_prime[i] == 0) {
            for (int j = i; j <= max_m; j += i) {
                if (min_prime[j] == 0) min_prime[j] = i;
            }
        }
        
        int p = min_prime[i];
        int x = i / p;
        
        if (x % p == 0) {
            mu[i] = 0;
        } else {
            mu[i] = -mu[x];
        }
    }
    
    // 预计算 2 的幂
    vector<int> pow2(max_m + 1);
    pow2[0] = 1;
    for (int i = 1; i <= max_m; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
    
    // 计算 dp[i] = sum_{j|i} mu[j] * 2^(i/j - 1)
    vector<int> dp(max_m + 1, 0);
    for (int i = 1; i <= max_m; i++) {
        for (int j = i; j <= max_m; j += i) {
            if (mu[i] == 1) {
                dp[j] = (dp[j] + pow2[j/i - 1]) % MOD;
            } else if (mu[i] == -1) {
                dp[j] = (dp[j] - pow2[j/i - 1] + MOD) % MOD;
            }
        }
    }
    
    // 计算前缀和
    vector<int> prefix(max_m + 1, 0);
    for (int i = 1; i <= max_m; i++) {
        prefix[i] = (prefix[i-1] + dp[i]) % MOD;
    }
    
    // 输出答案
    for (int m : queries) {
        cout << prefix[m] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

代码解释

$1$. 预处理莫比乌斯函数：

• 使用线性筛思想，通过最小质因子计算 $\mu(n)$
• $\mu(n) = 0$ 当 $n$ 有平方因子
• $\mu(n) = (-1)^k$ 当 $n$ 是 $k$ 个不同质数的乘积

$2$. 计算 dp 数组：

• $dp[i] = \sum_{j|i} \mu(j) \cdot 2^{\frac{i}{j}-1}$
• 使用倍数枚举，复杂度 $O(M \log M)$

$3$. 前缀和：

• $ans(m) = \sum_{i=1}^m dp[i]$
• 因为 $dp[i]$ 已经包含了所有长度为 $i$ 的好数组的计数

$4$. 时间复杂度：

• 预处理：$O(M \log M)$
• 每个查询：$O(1)$
• 总复杂度：$O(M \log M + t)$，其中 $M = 10^6$，$t \le 3 \times 10^5$

正确性证明概要

$1$. 等价性：好数组与严格递减的 $f(k)$ 序列一一对应 $2$. 计数转化：每个好数组对应一个因子链 $g_1 > g_2 > ... > g_n$，其中 $g_i$ 是后缀 $GCD$ $3$. 容斥原理：使用莫比乌斯反演去除不合法的重复计数 $4$. 最终公式：$dp[i]$ 恰好统计了长度为 $i$ 的好数组数量

这个解法充分利用了数论性质，在 $O(M \log M)$ 时间内完成所有预处理，能够轻松应对 $m \le 10^6$ 和 $t \le 3 \times 10^5$ 的极限数据。