P2241 统计方形（数据加强版）(矩形中的正方,长方形统计)

统计方形（数据加强版）

题目背景

1997年普及组第一题

题目描述

有一个 \(n \times m\) 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 \(n,m\)（\(n \leq 5000,m \leq 5000\)）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

样例 #1

样例输入 #1

2 3

样例输出 #1

8 10

这里直接给结论了

n*m的矩形中长方形(不包括正方形)的数量,等于子矩形的数量减去子正方形的数量

又子矩形的数量等于 \((m+1)\times m/2\times(n+1)\times n/2\),

这里把除以二拆成两个地方还可以防止爆int,或者爆long long

而子正方形的数量等于矩行中最大正方形的子正方形数量等于 \(\sum_{i=1}^{n}i\times (m-n+i)\)

换成代码就是:

for(int i=m,j=n;i>=1&&j>=1;i--,j--)zheng+=i*j;

得到子正方形的个数之后,就可以直接使用总的子矩形的数量,减去子正方形的数量得到子长方形的数量得到答案了.

int main() {
	long long n, m,c=0,z=0;
	cin >> n >> m;
	for (int i = n, j = m; i >= 1 && j >= 1; i--, j--)z += i * j;
	c = ((m + 1) * m/2) * ((n + 1) * n /2) - z;
	cout << z << " " << c << endl;
	return 0;
}