← 返回题目列表

Codeforces · 2147/G

G. 模块化四分法

中文机器翻译题面 查看原题

对于正整数 $$$a$$$,我们将递归 $$$\{b_n\}_{n\geq 0}$$$ 定义为 $$$b_n = a^{b_{n-1}}$$$,其中 $$$b_0 = 1$$$。

我们说正整数 $$$a$$$ 是 $$$m$$$-四定 如果序列$$$b$$$稳定到$$$1$$$模$$$m$$$,也就是说,存在$$$N \ge 0$$$,使得$$$b_n \equiv 1 \pmod m$$$对于所有$$$n \geq N$$$。

对于给定的 $$$m$$$,计算 $$$m$$$- 的密度四定 整数。这里,集合 $$$S$$$ 的密度是极限 $$\lim\limits_{n\rightarrow \infty}\frac{|S\cap [1,2,\ldots,n]|}{n}。$$ 非正式地,它是 $$$m$$$- 的正整数的“比例”四定.

可以证明(在该问题的约束下)密度是明确定义的并且始终是一个有理数,其分母不能被 $$$998\,244\,353$$$ 整除。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

数字 $$$m$$$ 将作为三个整数 $$$x$$$、$$$y$$$ 和 $$$z$$$ 的乘积提供给您。每个测试用例的第一行也是唯一一行包含三个整数 $$$x$$$、$$$y$$$、$$$z$$$ ($$$1\leq x,y,z \leq 10^6$$$, $$$m = xyz \geq 2$$$)。

输出

对于每个测试用例,打印 $$$m$$$- 的密度四定 整数($$$a$$$,使得其对应的序列 $$$b_n$$$ 收敛到 $$$1$$$ 模 $$$m$$$),模 $$$998\,244\,353$$$。

正式地,令 $$$M = 998\,244\,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot q \equiv p \pmod{M}$$$ 。

示例

输入
复制

5
5 1 1
5 2 1
23 1 1
10 10 2
9 3 37

输出
复制

499122177
299473306
893685162
913393583
705965601

注意

在第一个测试用例中,$$$m = 5$$$。例如,$$$a=1$$$ 是 $$$5$$$-四定 因为对于所有 $$$n$$$,$$$b_n = 1$$$。对于 $$$a= 8$$$,序列 $$$b$$$ 是 $$$[1, 8, 8^8, 8^{(8^8)}, \ldots]$$$,如果我们看它对 $$$5$$$ 取模的话,它是 $$$[1, 3, 1, 1, \ldots]$$$。可以证明,对于足够大的 $$$n$$$,序列始终是 $$$1 \pmod 5$$$,因此 $$$8$$$ 是 $$$5$$$-四定。对于 $$$a=10$$$,序列 $$$b$$$ 是 $$$[1, 10, 10^{10}, 10^{(10^{10})}, \ldots]$$$,如果我们对 $$$5$$$ 取模,则为 $$$[1, 0, 0, 0, \ldots]$$$。可以证明,对于足够大的 $$$n$$$,序列始终是 $$$0 \pmod 5$$$,因此 $$$10$$$ 不是 $$$5$$$-四定。第一个测试用例的答案是 $$$\frac{1}{2}$$$。

在第二个测试用例中,$$$m= 10$$$,答案是$$$\frac{1}{10}$$$。

在第三个测试用例中,$$$m= 23$$$,答案是$$$\frac{63}{506}$$$。

在第四个测试用例中,$$$m= 200$$$,答案是$$$\frac{1}{200}$$$。

在第五个测试用例中,$$$m= 999$$$,答案是$$$\frac{1}{222}$$$。