# 算法设计：矩形最大面积的正方形数量

2021年3月15日09:26:38 发表评论 772 次浏览

## 本文概述

``````Input: 9 6
Output: 6
Rectangle can be cut into squares of size 3.

Input: 4 2
Output: 2
Rectangle can be cut into squares of size 2.``````

s

ñ

。同样, 正方形的边应尽可能大, 因此, s应该是m和n的最大公约数。

s = gcd(m, n)

.

## C ++

``````// C++ code for calculating the
// number of squares
#include <bits/stdc++.h>
using namespace std;

// Function to find number of squares
int NumberOfSquares( int x, int y)
{
// Here in built c++ gcd function is used
int s = __gcd(x, y);

int ans = (x * y) / (s * s);

return ans;
}

// Driver code
int main()
{
int m = 385, n = 60;

// Call the function NumberOfSquares
cout << NumberOfSquares(m, n);

return 0;
}``````

## Java

``````// Java code for calculating
// the number of squares
import java.io.*;

class GFG
{
// Recursive function to
// return gcd of a and b
static int __gcd( int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0 )
return 0 ;

// base case
if (a == b)
return a;

// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}

// Function to find
// number of squares
static int NumberOfSquares( int x, int y)
{
// Here in built c++
// gcd function is used
int s = __gcd(x, y);

int ans = (x * y) / (s * s);

return ans;
}

// Driver Code
public static void main (String[] args)
{
int m = 385 , n = 60 ;

// Call the function
// NumberOfSquares
System.out.println(NumberOfSquares(m, n));
}
}

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

## Python3

``````# Python3 code for calculating
# the number of squares

# Recursive function to
# return gcd of a and b
def __gcd(a, b):

# Everything divides 0
if (a = = 0 or b = = 0 ):
return 0 ;

# base case
if (a = = b):
return a;

# a is greater
if (a > b):
return __gcd(a - b, b);
return __gcd(a, b - a);

# Function to find
# number of squares
def NumberOfSquares(x, y):

# Here in built PHP
# gcd function is used
s = __gcd(x, y);

ans = (x * y) / (s * s);

return int (ans);

# Driver Code
m = 385 ;
n = 60 ;

# Call the function
# NumberOfSquares
print (NumberOfSquares(m, n));

# This code is contributed
# by mit``````

## C#

``````// C# code for calculating
// the number of squares
using System;

class GFG
{

// Recursive function to
// return gcd of a and b
static int __gcd( int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;

// base case
if (a == b)
return a;

// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}

// Function to find
// number of squares
static int NumberOfSquares( int x, int y)
{
// Here in built c++
// gcd function is used
int s = __gcd(x, y);

int ans = (x * y) /
(s * s);

return ans;
}

// Driver Code
static public void Main ()
{
int m = 385, n = 60;

// Call the function
// NumberOfSquares
Console.WriteLine(NumberOfSquares(m, n));
}
}

// This code is contributed by ajit``````

## 的PHP

``````<?php
// PHP code for calculating
// the number of squares

// Recursive function to
// return gcd of a and b
function __gcd( \$a , \$b )
{
// Everything divides 0
if ( \$a == 0 || \$b == 0)
return 0;

// base case
if ( \$a == \$b )
return \$a ;

// a is greater
if ( \$a > \$b )
return __gcd( \$a - \$b , \$b );
return __gcd( \$a , \$b - \$a );
}

// Function to find
// number of squares
function NumberOfSquares( \$x , \$y )
{
// Here in built PHP
// gcd function is used
\$s = __gcd( \$x , \$y );

\$ans = ( \$x * \$y ) /
( \$s * \$s );

return \$ans ;
}

// Driver Code
\$m = 385;
\$n = 60;

// Call the function
// NumberOfSquares
echo (NumberOfSquares( \$m , \$n ));

// This code is contributed
// by akt_mit
?>``````

``924``