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

    ID: 12992 远端评测题 2000ms 512MiB 尝试: 1 已通过: 0 难度: 5 上传者: 标签>数学2023数论O2优化素数判断,质数,筛法逆元语言月赛

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

题目背景

材料 1:

请小心地计算下面的算式:138108÷6=?138 - 108 \div 6 = ?
你大概难以置信,这个算式的计算结果竟然是 5!5!

材料 2:

对于一个正整数 xx,$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 x!x!xx 的阶乘。
特别的,0!=10! = 1

显然,「138108÷6=5138 - 108 \div 6 = 5」是错误的,而「(138108)÷6=5(138 - 108) \div 6 = 5」是正确的,所以对材料 1 中的内容,部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。

然而,材料 1 最后一行的叹号并不是标点符号,而是材料 2 提到的「阶乘」。

考虑到这一点,「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。

题目描述

然而,此题可能与上面的题目背景关系不是很大。

我们会给你 TT 组数据,每组数据包括一个正整数 nn

对于每组数据,请你帮助求出满足以下条件的整数三元组 (x,y,z)(x, y, z) 的组数:

  1. x0x \geq 0z1z \geq 1
  2. xy÷z=n!x - y \div z = n!(xy)÷z=n!n(x - y) \div z = \dfrac{n!}{n}

由于答案可能过大,因此你需要输出答案对 998244353998244353 取模后的结果。

不难注意到答案有可能为 \infty,这时请按照「输出格式」要求进行处理。

请注意此处应满足 (xy)÷z=n!n(x - y) \div z = \dfrac{n!}{n} 而不是 =n= n

请注意这里的 ÷\div 不是向下取整的整除,这显然意味着你需要保证 y÷zy \div z(xy)÷z(x - y) \div z 为整数。

输入格式

输入共 T+1T + 1 行。

第一行为一个整数 TT

接下来 TT 行,每行一个整数 nn

输出格式

输出共 TT 行,每行一个整数或一个字符串。

对第 ii 行,如果对于输入数据中第 i+1i + 1 行的 nn,满足 xy÷z=n!x - y \div z = n!(xy)÷z=n!n(x - y) \div z = \dfrac{n!}{n} 的整数三元组 (x,y,z)(x, y, z) 有无限个,则输出一行 inf,否则输出满足条件的三元组的数量对 998244353998244353 取模后的结果。

3
2
3
4
1
3
6

提示

样例 1 解释

样例中的具体三元组如下:

nn 所有可能的三元组
22 (2,0,2)(2, 0, 2)
33 $\begin{matrix}(8, 4, 2) & (5, -5, 5) & (6, 0, 3)\end{matrix}$
44 $\begin{matrix}(19, -95, 19) & (21, -21, 7) & (24, 0, 4) \\ (27, 9, 3) & (20, -40, 10) & (36, 24, 2)\end{matrix}$

数据规模与约定

对于前 20%20\% 的数据,保证 T10T \leq 10n10n \leq 10

对于前 40%40\% 的数据,保证 n103n \leq 10 ^ 3

对于另外 20%20\% 的数据,保证 T=1T = 1

对于 100%100\% 的数据,保证 1T1051 \leq T \leq 10 ^ 51n1061 \leq n \leq 10 ^ 6