# 某岛

… : "…アッカリ～ン . .. . " .. .
May 1, 2012

# SPOJ 3179. Congruence Equation

… 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();
}
}
```