笔试题目（总结2）

题目：子矩阵之和
给定一个nm的矩阵，定义矩阵第i行第j列的值为gcd(i,j) (gcd为最大公因数)
定义子矩阵的和是其中所有元素之和 ，现在需要求所有kk的子矩阵的和的总和
1<=n,m<=5e3 1<=k<=min(n,m)

思路：
首先将所有子矩阵求和 拆分为两步 1.给定矩阵的左上角的x,y坐标，进行小矩阵的求和
2.在大矩阵中遍历 最大能达到的下标，可能超出大矩阵的范围则直接不予计算

代码解析：
第一步小矩阵求和

int sumk(int i, int j, int k)//i和j是第一个字符的x,y坐标
{
	int sumk = 0;
	for (int p = i; p < i + k; p++)
	{
		for (int q = j; q < j + k; q++)
		{
			sumk += gcd(p,q);
		}
	}
	return sumk;
}

上述gcd为求（坐标p，q的公因数）

int gcd(int m, int n)
{
	if (m % n == 0)
	{
		return n;
	}
	else
	{
		return gcd(n, m % n);
	}
}

第二步 遍历大矩阵中子矩阵能到达的范围

int main()
{
	int m, n, k;
	cin >> m >> n >> k;
	int sum1 = 0;
	for (int i = 1; i <= m - k+1; i++)
	{
		for (int j = 1; j <= n - k + 1; j++)
		{
			sum1 += sumk(i, j, k);
		}
	}
	cout << sum1 << endl;
	return 0;
}

最终的代码如下：

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> vec;
int gcd(int m, int n)
{
	if (m % n == 0)
	{
		return n;
	}
	else
	{
		return gcd(n, m % n);
	}
}
int sumk(int i, int j, int k)//i和j是第一个字符的x,y坐标
{
	int sumk = 0;
	for (int p = i; p < i + k; p++)
	{
		for (int q = j; q < j + k; q++)
		{
			sumk += gcd(p,q);
		}
	}
	return sumk;

}
int main()
{
	int m, n, k;
	cin >> m >> n >> k;
	int sum1 = 0;
	for (int i = 1; i <= m - k+1; i++)
	{
		for (int j = 1; j <= n - k + 1; j++)
		{
			sum1 += sumk(i, j, k);
		}
	}
	cout << sum1 << endl;
	return 0;
}