1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 #include using namespace std; using LL=long long; #define FOR(i,l,r) for(int i=(l);i<=(r);++i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) int(x.size()) templateauto&operator<<(ostream&o,pairp){return o<<'('<auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<= mod ? a - mod : a; } int powi(int a, int b) { if(b == 0) return 1; int x = powi(a, b / 2); x = mul(x, x); if(b % 2 == 1) x = mul(x, a); return x; } int inv(int x) { return powi(x, mod - 2); } int divide(int a, int b) { return mul(a, inv(b)); } int sub(int a, int b) { return add(a, mod - b); } using T = int; T determinant(vector>& a) { int n = ssize(a); T res = 1; REP(i, n) { int b = i; FOR(j, i + 1, n - 1) if(abs(a[j][i]) > abs(a[b][i])) b = j; if(i != b) swap(a[i], a[b]), res = sub(0, res); res = mul(res, a[i][i]); if (equal(res, 0)) return 0; FOR(j, i + 1, n - 1) { T v = divide(a[j][i], a[i][i]); if (not equal(v, 0)) FOR(k, i + 1, n - 1) a[j][k] = sub(a[j][k], mul(v, a[i][k])); } } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector t(n, 0); REP (i, n) cin >> t[i]; vector mat(n, vector (n, 0)); REP (i, n) REP (j, i) { int g = __gcd(t[i], t[j]); mat[i][j] = mat[j][i] = -g; mat[i][i] += g; mat[j][j] += g; } debug(mat); REP (i, n) mat[i].pop_back(); mat.pop_back(); debug(mat); cout << determinant(mat) << endl; }