### Brief description:

… n 元线性方程组的求解…

### Analysis:

.. (n + 1) 次 exGcd .. 判断是否有解 ..

之后… 系数向量用刚才的中间结果反代出即可。

#include <iostream> #include <cmath> using namespace std; #define DO(N) while(N--) #define REP(I, N) for (int I=0;I<int(N);++I) #define FOR(I, A, B) for (int I=int(A);I<int(B);++I) #define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I) #define FOR_1(I, A, B) for (int I=int(A);I<=int(B);++I) #define DWN_1(I, B, A) for (int I=int(B);I>=int(A);--I) template<class T> inline void RD(T &x){ char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0'; } template<class T> inline void RD(T &x0, T &x1){RD(x0), RD(x1);} template<class T> inline void RD(T &x0, T &x1, T &x2){RD(x0), RD(x1), RD(x2);} typedef long long LL; const int N = 100; int a[N], x[N], y[N]; int n, b, c, d, t, m, _; inline void INC(int &a, int b){ a += b; if (a >= m) a -= m; } inline void DEC(int &a, int b){ a -= b; if (a < 0) a += m; } inline void MUL(int &a, int b){ a = int(LL(a) * b % m); } inline int mul(int a, int b){ return int(LL(a) * b % m); } inline void exGcd(int m, int n, int &d, int& a, int & b){ int xx = 0, yy = 1, x = 1, y = 0, q; while (true){ q = m / n, m %= n; if (!m) {d = n, a = xx, b = yy; return;} DEC(x, mul(q, xx)), DEC(y, mul(q, yy)); q = n / m, n %= m; if (!n) {d = m, a = x, b = y; return;} DEC(xx, mul(q, x)), DEC(yy, mul(q, y)); } } void init(){ RD(n); REP(i, n) RD(a[i]); RD(b, m); b %= m; REP(i, n) a[i] %= m; } void solve(){ d = a[0], --n; REP(i, n){ exGcd(d, a[i+1], d, x[i], y[i]); } exGcd(d, m, d, t, _); if (b % d) { printf("NO\n"); return; } c = b / d; MUL(c, t), MUL(x[n-1], c), MUL(y[n-1], c); DWN(i, n, 1){ x[i+1] = y[i], MUL(x[i-1], x[i]), MUL(y[i-1], x[i]); } x[1] = y[0]; FOR(i, 0, n){ printf("%d ", x[i]); } printf("%d\n", x[n]); } int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int T; RD(T); DO(T){ init(); solve(); } }