# 算法题：如何计算矩形中的正方形数？

2021年3月25日11:46:30 发表评论 1,056 次浏览

## 本文概述

``````Input:  m = 2, n = 2
Output: 5
There are 4 squares of size 1x1 +
1 square of size 2x2.

Input: m = 4, n = 3
Output: 20
There are 12 squares of size 1x1 +
6 squares of size 2x2 +
2 squares of size 3x3.``````

## 推荐：请在"实践首先, 在继续解决方案之前。

[尺寸为1×1的m平方+尺寸为2×2的(m-1)平方+…+尺寸为m x m的1平方]

``````Total number of squares = m x (m+1) x (2m+1)/6 +
(n-m) x m x (m+1)/2

when n is larger dimension``````

.

## C ++

``````// C++ program to count squares
// in a rectangle of size m x n
#include<iostream>
using namespace std;

// Returns count of all squares
// in a rectangle of size m x n
int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n < m)
swap(m, n);

// Now n is greater dimension, // apply formula
return m * (m + 1) * (2 * m + 1) /
6 + (n - m) * m *(m + 1) / 2;
}

// Driver Code
int main()
{
int m = 4, n = 3;
cout << "Count of squares is "
<< countSquares(m, n);
}``````

## Java

``````// Java program to count squares
// in a rectangle of size m x n

class GFG
{
// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n < m)
{
// swap(m, n)
int temp = m;
m = n;
n = temp;
}

// Now n is greater dimension, // apply formula
return m * (m + 1 ) * ( 2 * m + 1 ) /
6 + (n - m) * m * (m + 1 ) / 2 ;
}

// Driver Code
public static void main(String[] args)
{
int m = 4 , n = 3 ;
System.out.println( "Count of squares is " +
countSquares(m, n));
}
}``````

## Python3

``````# Python3 program to count squares
# in a rectangle of size m x n

# Returns count of all squares
# in a rectangle of size m x n
def countSquares(m, n):

# If n is smaller, swap m and n
if (n < m):
temp = m
m = n
n = temp

# Now n is greater dimension, # apply formula
return ((m * (m + 1 ) * ( 2 * m + 1 ) /
6 + (n - m) * m * (m + 1 ) / 2 ))

# Driver Code
if __name__ = = '__main__' :
m = 4
n = 3
print ( "Count of squares is "
, countSquares(m, n))

# This code is contributed by mits.``````

## C#

``````// C# program to count squares in a rectangle
// of size m x n
using System;

class GFG {

// Returns count of all squares in a
// rectangle of size m x n
static int countSquares( int m, int n)
{
// If n is smaller, swap m and n
if (n < m)
{
// swap(m, n)
int temp = m;
m = n;
n = temp;
}

// Now n is greater dimension, apply
// formula
return m * (m + 1) * (2 * m + 1) / 6 +
(n - m) * m * (m + 1) / 2;
}

// Driver method
public static void Main()
{
int m = 4, n = 3;

Console.WriteLine( "Count of squares is "
+ countSquares(m, n));
}
}

//This code is contributed by vt_m.``````

## 的PHP

``````<?php
// PHP program to count squares
// in a rectangle of size m x n

// Returns count of all squares
// in a rectangle of size m x n
function countSquares( \$m , \$n )
{
// If n is smaller, swap m and n
if ( \$n < \$m )
list( \$m , \$n ) = array ( \$n , \$m );

// Now n is greater dimension, // apply formula
return \$m * ( \$m + 1) * (2 * \$m + 1) /
6 + ( \$n - \$m ) * \$m * ( \$m + 1) / 2;
}

// Driver Code
\$m = 4; \$n = 3;
echo ( "Count of squares is " . countSquares( \$m , \$n ));

// This code is contributed by Ajit.
?>``````

``Count of Squares is 20``

n *(n + 1)(3m-n + 1)/ 6

## C ++

``````// C++ program to count squares
// in a rectangle of size m x n
#include<iostream>
using namespace std;

// Returns count of all squares
// in a rectangle of size m x n
int countSquares( int m, int n)
{

// If n is smaller, swap m and n
if (n < m)
{
int temp = m;
m = n;
n = temp;
}

// Now n is greater dimension, // apply formula
return n * (n + 1) * (3 * m - n + 1) / 6;
}

// Driver Code
int main()
{
int m = 4, n = 3;
cout << "Count of squares is "
<< countSquares(m, n);
}

// This code is contributed by 29AjayKumar``````

## Java

``````// Java program to count squares
// in a rectangle of size m x n
import java.util.*;

class GFG
{

// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{

// If n is smaller, swap m and n
if (n < m)
{
int temp = m;
m = n;
n = temp;
}

// Now n is greater dimension, // apply formula
return n * (n + 1 ) * ( 3 * m - n + 1 ) / 6 ;
}

// Driver Code
public static void main(String[] args)
{
int m = 4 ;
int n = 3 ;
System.out.print( "Count of squares is " +
countSquares(m, n));
}
}

// This code is contributed by 29AjayKumar``````

## Python3

``````# Python3 program to count squares
# in a rectangle of size m x n

# Returns count of all squares
# in a rectangle of size m x n
def countSquares(m, n):

# If n is smaller, swap m and n
if (n < m):
temp = m
m = n
n = temp

# Now n is greater dimension, # apply formula
return n * (n + 1 ) * ( 3 * m - n + 1 ) / / 6

# Driver Code
if __name__ = = '__main__' :
m = 4
n = 3
print ( "Count of squares is" , countSquares(m, n))

# This code is contributed by AnkitRai01``````

## C#

``````// C# program to count squares
// in a rectangle of size m x n
using System;

class GFG
{

// Returns count of all squares
// in a rectangle of size m x n
static int countSquares( int m, int n)
{

// If n is smaller, swap m and n
if (n < m)
{
int temp = m;
m = n;
n = temp;
}

// Now n is greater dimension, // apply formula
return n * (n + 1) * (3 * m - n + 1) / 6;
}

// Driver Code
public static void Main(String[] args)
{
int m = 4;
int n = 3;
Console.Write( "Count of squares is " +
countSquares(m, n));
}
}

// This code is contributed by Rajput-Ji``````

``Count of Squares is 20``