luogu#P9007. [入门赛 #9] 最澄澈的空与海 (Hard Version)
[入门赛 #9] 最澄澈的空与海 (Hard Version)
题目背景
材料 1:
请小心地计算下面的算式:
你大概难以置信,这个算式的计算结果竟然是
材料 2:
对于一个正整数 ,$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 为 的阶乘。
特别的,。
显然,「」是错误的,而「」是正确的,所以对材料 1 中的内容,部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。
然而,材料 1 最后一行的叹号并不是标点符号,而是材料 2 提到的「阶乘」。
考虑到这一点,「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。
题目描述
然而,此题可能与上面的题目背景关系不是很大。
我们会给你 组数据,每组数据包括一个正整数 。
对于每组数据,请你帮助求出满足以下条件的整数三元组 的组数:
- ,。
- 且 。
由于答案可能过大,因此你需要输出答案对 取模后的结果。
不难注意到答案有可能为 ,这时请按照「输出格式」要求进行处理。
请注意此处应满足 而不是 。
请注意这里的 不是向下取整的整除,这显然意味着你需要保证 和 为整数。
输入格式
输入共 行。
第一行为一个整数 。
接下来 行,每行一个整数 。
输出格式
输出共 行,每行一个整数或一个字符串。
对第 行,如果对于输入数据中第 行的 ,满足 且 的整数三元组 有无限个,则输出一行 inf
,否则输出满足条件的三元组的数量对 取模后的结果。
3
2
3
4
1
3
6
提示
样例 1 解释
样例中的具体三元组如下:
所有可能的三元组 | |
---|---|
$\begin{matrix}(8, 4, 2) & (5, -5, 5) & (6, 0, 3)\end{matrix}$ | |
$\begin{matrix}(19, -95, 19) & (21, -21, 7) & (24, 0, 4) \\ (27, 9, 3) & (20, -40, 10) & (36, 24, 2)\end{matrix}$ |
数据规模与约定
对于前 的数据,保证 ,。
对于前 的数据,保证 。
对于另外 的数据,保证 。
对于 的数据,保证 ,。