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

External link:

http://www.spoj.pl/problems/DPEQN/

Posted by xiaodao
Category: SPOJ