P2241 統計方形（數據加強版）

題目背景

1997年普及組第一題

題目描述

有一個n*m方格的棋盤，求其方格包含多少正方形、長方形

輸入輸出格式

n,m因為原來數據太弱，現規定m小於等於5000，n小於等於5000（原來是100,100）

方格包含多少正方形、長方形

輸入輸出樣例

2 3

8 10

正方形個數

邊長為1 個數n*m

邊長為2 個數（n-1）*（m-1）

邊長為3 個數（n-2）*（m-2）

所以 邊長為min{n，m} 個數（m-min{n，m}+1）*（n-min{n，m}+1）

長方形加正方形個數

total=（1+2+3+…+n）*（1+2+3+…+m）

=（（1+n）*（1+m）*n*m)/4

長方形個數

上面兩式相減即可得出

所以思路就是 先算出正方形個數 然後用公式得出長方形和正方形個數總和 最後得到長方形個數

代碼很短

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int main()
 7 {
 8     long long n,m;
 9     long long ans1=1,ans2=0;
10     cin>>n>>m;
11     ans1=n*m;
12     long long p=(((1+n)*(1+m))*(n*m))/4;
13     while(n--&&m--)
14     {
15         ans1+=(n*m);
16     }
17     cout<<ans1<<" "<<p-ans1;
18 }