← 返回题目列表

AtCoder · dwacon5th_prelims_e

E. 循环 GCD

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

分数: 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)\) 时形成的循环及其美妙之处。

bdd8ce0a7db3b4f920b04551c60aa207.png