math/lgsFp.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Laufzeit: O(n^3)
void normalLine(ll n, ll line, ll p) { // Normalisiert Zeile line.
	ll factor = multInv(mat[line][line], p); // Implementierung von oben.
	for (ll i = 0; i <= n; i++) {
		mat[line][i] *= factor;
		mat[line][i] %= p;
	}
}

void takeAll(ll n, ll line, ll p) { // Zieht Vielfaches von line von allen anderen Zeilen ab.
	for (ll i = 0; i < n; i++) {
		if (i == line) continue;
		ll diff = mat[i][line];
		for (ll j = 0; j <= n; j++) {
			mat[i][j] -= (diff * mat[line][j]) % p;
			while (mat[i][j] < 0) {
				mat[i][j] += p;
			}
		}
	}
}

void gauss(ll n, ll p) { // nx(n+1)-Matrix, Koerper F_p.
	for (ll line = 0; line < n; line++) {
		normalLine(n, line, p);
		takeAll(n, line, p);
	}
}