diff options
Diffstat (limited to 'content/math/lgsFp.cpp')
| -rw-r--r-- | content/math/lgsFp.cpp | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp new file mode 100644 index 0000000..0241742 --- /dev/null +++ b/content/math/lgsFp.cpp @@ -0,0 +1,26 @@ +void normalLine(int line, ll p) { + ll factor = multInv(mat[line][line], p); + for (ll& x : mat[line]) x = (x * factor) % p; +} + +void takeAll(int n, int line, ll p) { + for (int i = 0; i < n; i++) { + if (i == line) continue; + ll diff = mat[i][line]; + for (int j = 0; j < sz(mat[i]); j++) { + mat[i][j] -= (diff * mat[line][j]) % p; + mat[i][j] = (mat[i][j] + p) % p; +}}} + +void gauss(int n, ll mod) { + vector<bool> done(n, false); + for (int i = 0; i < n; i++) { + int j = 0; + while (j < n && (done[j] || mat[j][i] == 0)) j++; + if (j == n) continue; + swap(mat[i], mat[j]); + normalLine(i, mod); + takeAll(n, i, mod); + done[i] = true; +}} +// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ |