CF1749D Counting Arrays

给定一个长度为 $n$ 的数组 $a$，元素编号从 $1$ 到 $n$。如果 $gcd(a_i, i) = 1$，则可以移除 $a$ 的第 $i$ 个元素（其中 $gcd$ 表示最大公约数）。每当移除一个元素后，其右侧的所有元素都会向左移动一个位置。 对于一个长度为 $n$ 的数组 $a$，如果存在一个长度为 $n$ 的数组 $b$，满足 $1 \le b_i \le n - i + 1$，且可以依次移除 $a$ 的第 $b_1$ 个元素、接着是第 $b_2$ 个元素，依此类推，直到数组为空，则称 $b$ 是 $a$ 的一个移除序列。例如，$a = [42, 314]$： - $[1, 1]$ 是一个移除序列：第一次移除第 $1$ 个元素，此时 $gcd(42, 1) = 1$，数组变为 $[314]$；再次移除第 $1$ 个元素，此时 $gcd(314, 1) = 1$，数组变为空。 - $[2, 1]$ 不是一个移除序列：第一次尝试移除第 $2$ 个元素，此时 $gcd(314, 2) = 1$ 不成立。 如果一个数组存在至少两个不同的移除序列，则称该数组是“模糊的”。例如，数组 $[1, 2, 5]$ 是模糊的：它有移除序列 $[3, 1, 1]$ 和 $[1, 2, 1]$。数组 $[42, 314]$ 不是模糊的：它只有一个移除序列 $[1, 1]$。 给定两个整数 $n$ 和 $m$，请计算长度在 $1$ 到 $n$ 之间、每个元素 $a_i$ 满足 $1 \le a_i \le m$ 的所有数组 $a$ 中，模糊数组的个数。

输入仅一行，包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$1 \le m \le 10^{12}$）。

输出一个整数，表示满足条件的模糊数组 $a$ 的个数。由于答案可能很大，请输出对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译