CF1749D Counting Arrays

给定一个数组 \(a\)，同时给定一个操作：选取一个数字 \(i\)，如果 \(\gcd(a_i,i) = 1\)，我们就可以将当前的第 \(i\) 位上的数字 \(a_i\) 移除掉，而后面的数字会以此补上空缺。

定义一个序列 \(b\) 为一个“移除序列”，当且仅当我们可以通过依次选取 \(b_1\) 到 \(b_n\) 进行上面所说的操作，最终将整个 \(a\) 数组移除。

定义一个数组 \(a\) 是不好的，当且仅当其有不止一个移除序列。你需要统计出长度为 \([1,n]\) 范围内正整数的，各元素为 \([1,m]\) 范围内正整数的不好的序列的个数，模 \(998244353\)。

\(n \le 3 \times 10^5\)，\(m \le 10^{12}\)。

题意是抄翻译的请见谅。

首先一个序列最少也会有一个删除序列，因为可以把下标 \(1\) 对应的数一个一个删掉。题目中规定一个数 \(a_i\) 可以在位置 \(i\) 被删掉，当且仅当 \(a_i \perp i\)，然后一个关键观察是，在原数组中位置为 \(i\) 的数，如果没有被途中删除的话，那么在删除过程中一定会经过 \([1, i]\) 的所有位置，那么我们发现，一个数不能在途中被删掉，当且仅当对于任意 \(j \in [2, i]\)，都有 \(a_i \not \perp j\)，即 \(\gcd(a_i, j) \not = 1\)。

正难则反，将问题转化为求好的方案数。由上边的分析我们得到，一个序列是好的，当且仅当对于任意 \(2 \le j \le i \le n\)，都有 \(\gcd(a_i, j) \not = 1\)，也就意味着 \(a\) 中的所有数都只能在位置 \(1\) 被删掉，也就只有一种删除序列了。通过算数基本定理，满足对于所有 \(i \in [2, n]\) 的 \(i\)，满足 \(\gcd(x, i) \not = 1\) 的最小 \(x\) 为 \([2, n]\) 中所有出现过的质因子的乘积（每个只乘一次）。那么位置 \(i\) 上满足上述条件的数的个数就等于 \(\lfloor \dfrac{m}{\prod_{j \in \mathbb{P} \land j \le i} j} \rfloor\)。那么根据乘法原理，直接对 \([1, n]\) 累乘即可得到好的序列的个数。

因为 \(m\) 太大了可能会出现 long long 溢出，因此需要龟速乘。时间复杂度线性对数。

代码。