题解 | 数方格

题目大意

求出一个 $n\times m$ 的矩阵内有多少个正方形。

解题思路

先求出一个 $n\times m$ 的矩阵内有多少个边长为 $x$ 的正方形，横坐标有 $n-x+1$ 种情况，纵坐标有 $m-x+1$ 种情况，所以一共有 $(n-x+1)(m-x+1)$ 种情况。枚举正方形的边长 $i$，再依次累加 $(n-i+1)(m-i+1)$，而正方形边长的最大值为 $n$ 和 $m$ 的最小值，因为如果 $i>min(n,m)$，那么这个矩阵就放不下这个正方形了。

参考代码

#include<iostream>
#define ll long long
using namespace std;
ll n,m,ans;
int main(){
    cin>>n>>m;
    for(ll i=1;i<=min(n,m);++i){
    	ans+=(n-i+1)*(m-i+1);
	}
	cout<<ans;
	return 0;
}