整数gauss消元（辗转相除）

int mat[10][10], ans[10];

inline void mul(int *a, int t) {
	F(i, 1, n+1) a[i] *= t;
}

inline void sub(int *a, int *b, int t) {
	F(i, 1, n+1) a[i] -= b[i]*t;
}

void gauss() {
	F(k, 1, n) {
		F(i, k, n) {
			if (mat[i][k]) {
				if (i != k) swap(mat[i], mat[k]);
				break;
			}
		}
		F(i, k+1, n) {
			int *a = mat[k], *b = mat[i];
			if (a[k] < 0) mul(a, -1);
			if (b[k] < 0) mul(b, -1);
			while (a[k]) {
				if (a[k] > b[k]) swap(a, b);
				sub(b, a, b[k]/a[k]);
				swap(a, b);
			}
			swap(a, b);
		}
	}
	G(i, n, 1) {
		ans[i] = mat[i][n+1];
		F(j, i+1, n) {
			ans[i] -= ans[j]*mat[i][j];
		}
		ans[i] /= mat[i][i];
	}
}