枚举-统计方形

题目

题目描述

有一个n*m方格的棋盘，求其方格包含多少正方形、长方形（此处长方形不包含正方形）

输入格式

输入存在多组测试数据。每组测试数据输入两个整数n,m，数字不超过5000

输出格式

对于每组数据输出一行包含两个整数，分别表示正方形数目和长方形数目

输入样例

2 3

输出样例

8 10

分析

首先计算对于n * m的矩形，一共有多少个子矩形

\(从选择边的角度，可以选边长从1到n，一共1 + 2 + …… + n = \frac{(n + 1)(n)}{2}\)

接着计算对于n * m的矩形，一共有多少个子正方形

从选择边的角度，可以选的边的长度从1到min(n, m)

正方形的边长每增加1，母矩形的长可以放下对应边长的正方形的个数就减少1，宽同理

最后用总矩形数量减去总正方形数量就得到总长方形数量

第一次写错误

计算总矩形数量和总正方形数量必须要开long才放得下

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()) {
            int n = input.nextInt();
            int m = input.nextInt();
            long nSide = (n + 1) * n / 2;    //n方向可以选出的边数，等差求和
            long mSide = (m + 1) * m / 2;    //m方向可以选出的边数，等差求和
            long totalMatrix = nSide * mSide;
            int nSqNum = n;     //n方向可以放下正方形的数量
            int mSqNum = m;     //m方向可以放下正方形的数量
            long sqNum = 0;
            for(int sqLength = 1; sqLength <= Math.min(n, m); sqLength++) {   //子正方形的边长
                sqNum += nSqNum * mSqNum;
                nSqNum--;
                mSqNum--;
            }
            long matrixNum = totalMatrix - sqNum;
            System.out.format("%d %d\n", sqNum, matrixNum);
        }
        input.close();        
    }
}