SP4195 MSE08H - GCD Determinant 题解

题目链接：MSE08H - GCD Determinant

题意：

给定 \(n\) 个数 \(x_1,x_2,\cdots,x_n\) ，求 \[ \det A = \left|\begin{array}{ccccc} \operatorname{gcd}\left(x_1, x_1\right) & \operatorname{gcd}\left(x_1, x_2\right) & \operatorname{gcd}\left(x_1, x_3\right) & \ldots & \operatorname{gcd}\left(x_1, x_n\right) \\ \operatorname{gcd}\left(x_2, x_1\right) & \operatorname{gcd}\left(x_2, x_2\right) & \operatorname{gcd}\left(x_2, x_3\right) & \ldots & \operatorname{gcd}\left(x_2, x_n\right) \\ \operatorname{gcd}\left(x_3, x_1\right) & \operatorname{gcd}\left(x_3, x_2\right) & \operatorname{gcd}\left(x_3, x_3\right) & \ldots & \operatorname{gcd}\left(x_3, x_n\right) \\ \vdots & \vdots & \vdots & & \vdots \\ \operatorname{gcd}\left(x_n, x_1\right) & \operatorname{gcd}\left(x_n, x_2\right) & \operatorname{gcd}\left(x_n, x_3\right) & \ldots & \operatorname{gcd}\left(x_n, x_n\right) \end{array}\right| \] \(1 \le n \le 10^3,~x_i \le 2\times 10^9\) 。

根据 Smith’s determinant（GCD矩阵的行列式） 我们推导出了 \[ \left|\begin{array}{cccc} \operatorname{gcd}(1,1) & \operatorname{gcd}(1,2) & \ldots & \operatorname{gcd}(1, n) \\ \operatorname{gcd}(2,1) & \operatorname{gcd}(2,2) & \ldots & \operatorname{gcd}(2, n) \\ \vdots & \vdots & & \vdots \\ \operatorname{gcd}(n, 1) & \operatorname{gcd}(n, 2) & \ldots & \operatorname{gcd}(n, n) \end{array}\right|=\varphi(1) \varphi(2) \cdots \varphi(n) \] 本题中把矩阵变成了 \(A=[a_{i,j}],~a_{i,j}=\gcd(x_i,x_j)\) ，其实是一样的

我们只需要在证明中更改矩阵 \(B\)​ 即可 \[ B=\left[b_{i, j}\right], \quad b_{i, j}= \begin{cases}J_r(x_i) & \text { if } i \mid j \\ 0 & \text { otherwise }\end{cases} \] 即可得到 \[ \left|\begin{array}{ccccc} \operatorname{gcd}\left(x_1, x_1\right) & \operatorname{gcd}\left(x_1, x_2\right) & \operatorname{gcd}\left(x_1, x_3\right) & \ldots & \operatorname{gcd}\left(x_1, x_n\right) \\ \operatorname{gcd}\left(x_2, x_1\right) & \operatorname{gcd}\left(x_2, x_2\right) & \operatorname{gcd}\left(x_2, x_3\right) & \ldots & \operatorname{gcd}\left(x_2, x_n\right) \\ \operatorname{gcd}\left(x_3, x_1\right) & \operatorname{gcd}\left(x_3, x_2\right) & \operatorname{gcd}\left(x_3, x_3\right) & \ldots & \operatorname{gcd}\left(x_3, x_n\right) \\ \vdots & \vdots & \vdots & & \vdots \\ \operatorname{gcd}\left(x_n, x_1\right) & \operatorname{gcd}\left(x_n, x_2\right) & \operatorname{gcd}\left(x_n, x_3\right) & \ldots & \operatorname{gcd}\left(x_n, x_n\right) \end{array}\right| =\varphi(x_1) \varphi(x_2) \cdots \varphi(x_n) \] 时间复杂度 \(\mathcal{O}(qn \log V)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int phi(int n)
{
    int ans = n;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}
int n, r;
const int mod = 1e9 + 7;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n)
    {
        r = 1;
        for(int i = 1, x; i <= n; i++) {
            cin >> x, r = r * phi(x) % mod;
        }
        cout << r << '\n';
    }
    return 0;
}