统计方形(数据加强版)
题目背景
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;
}
标签:加强版,int,P2241,长方形,long,times,正方形,矩形,统计
From: https://www.cnblogs.com/zhywyt/p/17086390.html