分数: 1000 点
问题陈述
二王后君有\(N\)只鸡作为他的宠物。这些鸡用数字\(1\)到\(N\)来标识,第\(i\)只鸡的大小是一个正整数\(a_i\)。
\(N\) 只鸡决定握住彼此的手(翅膀)并形成一些循环。形成循环的方式由 \(1, \ldots , N\) 的排列 \(p\) 表示。小鸡\(i\)抓住小鸡\(p_i\)的右手。鸡可能会握住自己的手。
让我们定义 循环 包含鸡 \(i\) 作为由鸡 \(p_i, p_{p_i}, \ldots, p_{\ddots_i} = i\) 组成的集合。可以证明,每只鸡拿了一些鸡的手后,这\(N\)只鸡就可以分解成循环。
的 树的 美女 二进制字符串 $$$z$$$ 的 形成循环的一种方式\(f(p)\)被定义为每个循环中最小的鸡的尺寸的乘积。 设 \(b_i \ (1 \leq i \leq N)\) 为在上述过程中形成 \(i\) 个循环的所有可能排列 \(p\) 中 \(f(p)\) 的总和。
找到 \(b_1, b_2, \ldots, b_N\) 的最大公约数并打印它 \({\rm mod} \ 998244353\)。
约束
- \(1 \leq N \leq 10^5\)
- \(1 \leq a_i \leq 10^9\)
- 输入中给出的所有数字均为整数
输入
输入由标准输入按以下格式给出:
\(N\) \(a_1\) \(a_2\) \(\ldots\) \(a_N\)
输出
打印答案。
示例输入 1
2 4 3
示例输出 1
3
在这种情况下,\(N = 2, a = [ 4, 3 ]\)。
对于排列 \(p = [ 1, 2 ]\),做了一个唯一鸡的循环 \(1\) 和一个唯一鸡的循环 \(2\),因此 \(f([1, 2]) = a_1 \times a_2 = 12\)。
对于排列 \(p = [ 2, 1 ]\),形成两只鸡 \(1\) 和 \(2\) 的循环,最小的鸡的大小为 \(a_2 = 3\),因此 \(f([2, 1]) = a_2 = 3\)。
现在我们知道 \(b_1 = f([2, 1]) = 3, b_2 = f([1, 2]) = 12\),而 \(b_1\) 和 \(b_2\) 的最大公约数是 \(3\)。
示例输入 2
4 2 5 2 5
示例输出 2
2
总是有 \(N!\) 种排列,因为相同大小的鸡可以彼此区分。
下图分别展示了当 \(p = (2, 1, 4, 3)\) 和 \(p = (3, 4, 1, 2)\) 时形成的循环及其美妙之处。