高斯消元法_9阶矩阵怎么解-CSDN博客

本文介绍了如何使用高斯消元法解决线性方程组，特别是在0-1矩阵问题上的应用。作者提供了一个泛型模板类`GaussElimination`，用于处理不同数据类型的矩阵，并实现了解决0-1矩阵问题的子类`GaussEliminationXor`。文章通过两个在线判题平台（HDU 5833和UVA 11542）的实例，展示了如何将高斯消元法应用于求解完全平方数的组合计数问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一，高斯消元法解方程组

二，0-1矩阵

三，OJ实战

HDU 5833 Zhu and 772002

UVA 11542 Square

一，高斯消元法解方程组

求解方程组整体可以分为2步，先化简增广矩阵，再根据化简后的矩阵求出可能存在的一个解。

（1）标准化简操作：从左往右依次找到每一列的第一个不为0的元素（如果有的话），用消元法消去这一列其他行的不为0的数。

（2）求出可能存在的一个解：根据化简后的矩阵，从下往上依次求解。

下面的模板代码我做了3个抽象：

（1）化简操作不感知矩阵类型（系数矩阵or增广矩形or任意），化简的同时顺便求出矩阵的秩。所以这个代码也可以用来求任意矩阵的秩r，经过换行之后，前r行就是挑选出的行。

（2）矩阵的数据类型是泛型的，实际上应该是三种：浮点数，有理数，0-1异或。异或即mod 2，可以推广到mon p，但是需要逆元计算，我暂时懒得写。

（3）计算是泛型的，泛型的zero巧妙的用sub函数推导出来。


#include <iostream>
#include <vector>
using namespace std;

template<typename T = int>
class GaussElimination
{
public:
	int solve(vector<vector<T>>& v)//化简并返回秩
	{
		T zero = sub(T{}, T{});
		int ans = 0, row = v.size(), col = v[0].size();
		for (int i = 0; i < col; i++)for (int j = ans; j < row; j++)
		{
			if (v[j][i] == zero)continue;
			vector<T> vtmp = v[ans];
			v[ans] = v[j], v[j] = vtmp;
			div(v[ans], v[ans][i]);
			for (int k = j + 1; k < row; k++) {
				if (v[k][i] == zero)continue;
				div(v[k], v[k][i]);
				for (int xi = i; xi < col; xi++)v[k][xi] = sub(v[k][xi], v[ans][xi]);
			}
			ans++;
			break;
		}
		return ans;
	}
	vector<int> getAns(vector<vector<int>>& v)
	{
		int row = v.size(), col = v[0].size();
		solve(v);
		T zero = sub(T{}, T{});
		vector<int>ans(col - 1, zero);
		for (int r = v.size() - 1; r >= 0; r--) {
			int id = 0;
			for (int c = 0; c < col; c++) {
				if (v[r][c] == zero)continue;
				id = c;
				break;
			}
			if (id == col - 1) {
				return vector<int>{};//无解
			}
			T s = v[r][col - 1];
			for (int c = id + 1; c < col - 1; c++)s = sub(s, mul(v[r][c], ans[c]));
			ans[id] = s;
		}
		return ans;
	}
protected:
	virtual T sub(T a, T b) = 0;
	virtual T div(T a, T b) = 0;
	virtual T mul(T a, T b) = 0;
private:
	void div(vector<T>& v, T num)
	{
		for (auto& vi : v)vi = div(vi, num);
	}
};

二，0-1矩阵

class GaussEliminationXor :public GaussElimination<int>
{
public:
	int sub(int a, int b)
	{
		return a ^ b;
	}
	int div(int a, int b)
	{
		return a; // b=1
	}
	int mul(int a, int b)
	{
		return a * b;
	}
};

三，OJ实战

HDU 5833 Zhu and 772002

题目：

Description

Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem.

But 772002 has a appointment with his girl friend. So 772002 gives this problem to you.

There are numbers . The value of the prime factors of each number does not exceed , you can choose at least one number and multiply them, then you can get a number .

How many different ways of choices can make is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007
Input

First line is a positive integer T, represents there are T test cases.

For each test case:

First line includes a number ，next line there are numbers .
Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by 1000000007
Sample Input

2
3
3 3 4
3
2 2 2
Sample Output

Case #1:
3
Case #2:
3

题意：给定数组，问有多少种方法可以选出任意个数，乘积是完全平方数。

我的思路是，把2000以内的303个素数用数组存起来，然后把输入的n个数表示成n行，每一行都是303个0或者1。

1表示的是这个数中这个素因子的次数为奇数，0表示为偶数。

现在就是要求，有多少种选行的方法，使得行的和全为0。

这里的和，可以理解为普通的和mod2，也可以理解为异或。

然后怎么求呢，这就是高斯消元法了。

本来应该能对的，可惜我傻了，偷懒了，没有真的把每个数表示成1个数组，用了差不多的形式。

然后就悲催了，那么多素数，它们的积一下就超了long long了，然后就wrong answer了。

然后现在又按照二维数组来写，写完就AC了。

代码：


#include <iostream>
#include <vector>
using namespace std;


int main()
{
	int prime[303] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 
		101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 
		211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 
		401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 
		601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 
		809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 
		1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 
		1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 
		1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 
		1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 
		1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };
	const int r = 300, c = 303;
	vector<vector<int>>x(300, vector<int>(303));
	int t, n, p;
	long long a;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> n;
		int row = 0;
		while (n--)
		{
			cin >> a;
			for (int i = 0; i < 303; i++)
			{
				p = prime[i];
				while (a % (p*p) == 0)a /= (p*p);
				x[row][i] = (a%p == 0);
			}
			row++;
		}
		int dr = row - GaussEliminationXor().solve(x);
		int r = 1;
		while(dr--)r = r * 2 % 1000000007;
		printf("Case #%d:\n%d\n", i, (r - 1) % 1000000007);
	}
	return 0;
}

UVA 11542 Square

题目：

这个题目完全就是HDU - 5833 Zhu and 772002 的简化版

所以我直接把那个题目的代码改了一丢丢就可以AC了。

代码：

#include <iostream>
#include <vector>
using namespace std;



int main()
{
	int prime[303] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
		101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
		211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
		401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
		601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
		809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
		1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
		1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
		1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
		1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
		1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };
	int t, n, p;
	long long a;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> n;
		vector<vector<int>>x(n, vector<int>(303));
		int row = 0;
		while (n--)
		{
			cin >> a;
			for (int i = 0; i < 303; i++)
			{
				p = prime[i];
				while (a % (p * p) == 0)a /= (p * p);
				x[row][i] = (a % p == 0);
			}
			row++;
		}
		int dr = row - GaussEliminationXor().solve(x);
		long long r = 1;
		while (dr--)r = r * 2;
		cout << r - 1 << endl;
	}
	return 0;
}

四，其他实战

黑白无双