整数gauss消元（辗转相除）

__xzm__ · 2025-06-14 18:26:55 · 算法·理论

用的时候注意改 数组大小 和 n，如果题目有取模记得加取模。

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];
    }
}