/ 
Time Limit: 2.525 sec / Memory Limit: 1024 MB
配点 : 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\) 羽全てのニワトリが手を取ったとき、\(N\) 羽のニワトリたちは何個かの輪に分割できることが証明できます。
輪の作り方の 美しさ \(f(p)\) はそれぞれの輪に含まれる最も小さいニワトリの大きさの積で定義されます。
\(1 \leq i \leq N\) を満たす \(i\) について、上の方法で輪が \(i\) 個できるような順列 \(p\) について \(f(p)\) を足し合わせたものを \(b_i\) とします。
\(b_1, \ldots, b_N\) の最大公約数を、modulo \(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)\) の場合の輪の作り方および美しさである。
Score : 1000 points
Problem Statement
Niwango-kun has \(N\) chickens as his pets. The chickens are identified by numbers \(1\) to \(N\), and the size of the \(i\)-th chicken is a positive integer \(a_i\).
\(N\) chickens decided to take each other's hand (wing) and form some cycles. The way to make cycles is represented by a permutation \(p\) of \(1, \ldots , N\). Chicken \(i\) takes chicken \(p_i\)'s left hand by its right hand. Chickens may take their own hand.
Let us define the cycle containing chicken \(i\) as the set consisting of chickens \(p_i, p_{p_i}, \ldots, p_{\ddots_i} = i\). It can be proven that after each chicken takes some chicken's hand, the \(N\) chickens can be decomposed into cycles.
The beauty \(f(p)\) of a way of forming cycles is defined as the product of the size of the smallest chicken in each cycle. Let \(b_i \ (1 \leq i \leq N)\) be the sum of \(f(p)\) among all possible permutations \(p\) for which \(i\) cycles are formed in the procedure above.
Find the greatest common divisor of \(b_1, b_2, \ldots, b_N\) and print it \({\rm mod} \ 998244353\).
Constraints
- \(1 \leq N \leq 10^5\)
- \(1 \leq a_i \leq 10^9\)
- All numbers given in input are integers
Input
Input is given from Standard Input in the following format:
\(N\) \(a_1\) \(a_2\) \(\ldots\) \(a_N\)
Output
Print the answer.
Sample Input 1
2 4 3
Sample Output 1
3
In this case, \(N = 2, a = [ 4, 3 ]\).
For the permutation \(p = [ 1, 2 ]\), a cycle of an only chicken \(1\) and a cycle of an only chicken \(2\) are made, thus \(f([1, 2]) = a_1 \times a_2 = 12\).
For the permutation \(p = [ 2, 1 ]\), a cycle of two chickens \(1\) and \(2\) is made, and the size of the smallest chicken is \(a_2 = 3\), thus \(f([2, 1]) = a_2 = 3\).
Now we know \(b_1 = f([2, 1]) = 3, b_2 = f([1, 2]) = 12\), and the greatest common divisor of \(b_1\) and \(b_2\) is \(3\).
Sample Input 2
4 2 5 2 5
Sample Output 2
2
There are always \(N!\) permutations because chickens of the same size can be distinguished from each other.
The following picture illustrates the cycles formed and their beauties when \(p = (2, 1, 4, 3)\) and \(p = (3, 4, 1, 2)\), respectively.