GCD Determinant

Xem dạng PDF
Gửi bài giải
Điểm: 1,51 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
Southeastern European 2008
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    nguyendailam0719  đã bình luận lúc 23, Tháng 4, 2026, 9:38

    code AC

    #include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1000000007;

ll phi(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            res = res / i * (i - 1);
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n) { 
        vector<ll> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        ll ans = 1;
        for (int i = 0; i < n; i++) {
            ans = (ans * phi(a[i])) % MOD;
        }

        cout << ans << '\n';
    }
}