GCD Determinant

View as PDF

Submit solution

Points: 1.51 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Southeastern European 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tập ~S = \{x_1, x_2, \dots, x_n\}~ là thừa số đóng (factor closed) nếu với mỗi ~x_i \in S~ và với mỗi ước số ~d~ của ~x_i~ ta có ~d \in S~. Xét ma trận ~GCD(S) = s_{ij}~, với ~s_{ij} = GCD(x_i, x_j)~ -- USCLN của ~x_i~ và ~x_j~. Cho một tập thừa số đóng, hãy tính định thức của nó. (Kiến thức đại học).

~D_n = \begin{array}{|lllll|} gcd(x_1, x_1) & gcd(x_1, x_2) & gcd(x_1, x_3) & \dots & gcd(x_1, x_n) \\ gcd(x_2, x_1) & gcd(x_2, x_2) & gcd(x_2, x_3) & \dots & gcd(x_2, x_n) \\ gcd(x_3, x_1) & gcd(x_3, x_2) & gcd(x_3, x_3) & \dots & gcd(x_3, x_n) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ gcd(x_n, x_1) & gcd(x_n, x_2) & gcd(x_n, x_3) & \dots & gcd(x_n, x_n) \\ \end{array}~

Input

Gồm vài test case, mỗi test case bắt đầu là ~1~ số nguyên ~n~ ~(0 < n < 1000)~, số phần tử của ~S~. Dòng tiếp theo là ~n~ số của ~S~: ~x_1~, ~x_2~, ..., ~x_n~, ~0 < x_i < 2 \times 10^{9}~.

Output

VỚi mỗi test tính ~D_n \bmod 1000000007~. (~D_n~: định thức của test thứ ~n)~.

Sample Input

2 
1 2 
3 
1 3 9 
4 
1 2 3 6

Sample Output

1
12
4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.