A2.数方格题解（简单易懂）

题目描述

给定一个 $n \times m$ 的方格网格，求其中所有正方形的总数量。

问题分析

在一个 $n \times m$ 的网格中，我们可以找到大小不同的正方形。关键是要确定：

• 对于某个特定边长的正方形，它的左上角顶点可以放在哪些位置？
• 所有可能的边长有哪些？

1. 确定边长范围

在一个 $n \times m$ 的网格中，正方形的边长 $k$ 必须同时满足：

• $k \leq n$（不能超过行数）
• $k \leq m$（不能超过列数）
  因此，边长 $k$ 的取值范围为：$1 \leq k \leq \min(n, m)$

2. 计算边长为 $k$ 的正方形数量

对于边长为 $k$ 的正方形：

• 水平方向：左上角顶点的横坐标 $x$ 可以取 $1, 2, ..., n-k+1$，共 $n-k+1$ 种可能
• 垂直方向：左上角顶点的纵坐标 $y$ 可以取 $1, 2, ..., m-k+1$，共 $m-k+1$ 种可能
  根据乘法原理，边长为 $k$ 的正方形数量为：

$$(n-k+1) \times (m-k+1)$$

3. 计算总数

总的正方形数量为所有不同边长的正方形数量之和：

$$\text{ans} = \sum_{k=1}^{\min(n,m)} (n-k+1) \times (m-k+1)$$

使用循环即可解决，时间复杂度为 $O(nm)$，可以通过。
参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long ans;//十年OI一场空，不开long long见祖宗
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);//输入输出优化，可以省略
    cin>>n>>m;
    while(n>0&&m>0){
        ans+=n*m;
        n--;
        m--;
    }
    cout<<ans<<endl;
	return 0;
}