Número de rectángulos con área determinada en una cuadrícula N*M

Dados tres enteros positivos N , M y A , la tarea es contar el número de rectángulos con área igual a A presentes en una cuadrícula M * N.

Ejemplos:

Entrada: N = 2, M = 2, A = 2 
Salida: 4 
Explicación: 
En la cuadrícula dada de tamaño 2 × 2, se pueden inscribir 2 rectángulos de dimensión 2 × 1 y 2 rectángulos de dimensión 1 × 2. 
Por lo tanto, la salida requerida es 4.

Entrada: N = 2, M = 2, A = 3
Salida: 0
Explicación: 
Los rectángulos posibles con área A (= 3) son de dimensiones 1 × 3 o 3 × 1.
Pero, la longitud máxima de un lado en el cuadrícula solo puede ser 2. Por lo tanto, no se pueden inscribir rectángulos dentro de la cuadrícula.

Enfoque: El problema se puede resolver con base en las siguientes observaciones:

El número total de formas de seleccionar un segmento de longitud X en el segmento de longitud M es igual a (M – X + 1) . 
Por lo tanto, el recuento total de rectángulos de tamaño X * Y en el rectángulo de tamaño M * N es igual a (M – X + 1) * (N – Y + 1) .

Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [1, √A] . Para cada i- ^ésima iteración, encuentre todos los valores posibles de largo y ancho de los rectángulos, digamos {i, (A / i)} o { (A / i), i } dentro de la cuadrícula dada.
• Iterar sobre todos los valores posibles de longitud, digamos X y ancho, digamos Y , e incremente el recuento de rectángulos en (M – X + 1) * (N – Y + 1) .
• Finalmente, imprima el conteo obtenido.

A continuación se muestra la implementación del enfoque anterior:

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of rectangles
// in an M * N grid such that the area of
// the rectangles is equal to A
int count_number(int N, int M, int A)
{
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    vector<pair<int, int> > v;
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++) {
 
        // If N is divisible by i
        if (N % i == 0) {
 
            // Stores length of the rectangle
            int length = i;
 
            // Stores breadth of the rectangle
            int breadth = A / i;
 
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth) {
 
                // Insert { length, breadth }
                v.push_back({ length, breadth });
 
                // Insert { breadth, length }
                v.push_back({ breadth, length });
            }
            else {
 
                // Insert { length, breadth}
                // because both are equal
                v.push_back({ length, breadth });
            }
        }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    long long total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    for (auto it : v) {
 
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        int num1 = (max(0, M - it.first + 1));
 
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        int num2 = (max(0, N - it.second + 1));
 
        // Update total
        total += (num1 * num2);
    }
 
    return total;
}
 
// Drivers Code
int main()
{
 
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    cout << count_number(N, M, A) << endl;
}

// Java program of the above approach
import java.util.*;
class GFG
{
     
static class pair
{
    int first, second;
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
   
// Function to find the count of rectangles
// in an M * N grid such that the area of
// the rectangles is equal to A
static int count_number(int N, int M, int A)
{
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    Vector<pair> v = new Vector<pair>();
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++)
    {
 
        // If N is divisible by i
        if (N % i == 0)
        {
 
            // Stores length of the rectangle
            int length = i;
 
            // Stores breadth of the rectangle
            int breadth = A / i;
 
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth)
            {
 
                // Insert { length, breadth }
                v.add(new pair(length, breadth));
 
                // Insert { breadth, length }
                v.add(new pair(breadth, length));
            }
            else
            {
 
                // Insert { length, breadth}
                // because both are equal
                v.add(new pair(length, breadth));
            }
        }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    int total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    for (pair it : v)
    {
 
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        int num1 = (Math.max(0, M - it.first + 1));
 
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        int num2 = (Math.max(0, N - it.second + 1));
 
        // Update total
        total += (num1 * num2);
    }
    return total;
}
 
// Drivers Code
public static void main(String[] args)
{
 
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    System.out.print(count_number(N, M, A) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program of the above approach
 
# Function to find the count of rectangles
# in an M * N grid such that the area of
# the rectangles is equal to A
def count_number(N, M, A):
 
    # Stores all possible values of length
    # and breadth whose area equal to A
    v = []
 
    # Calculate all divisors of A
    for i in range(1, A + 1):
 
        if i * i > A:
            break
 
        # If N is divisible by i
        if (N % i == 0):
 
            # Stores length of the rectangle
            length = i
 
            # Stores breadth of the rectangle
            breadth = A // i
 
            # If length of rectangle is not
            # equal to breadth of rectangle
            if (length != breadth):
 
                # Insert { length, breadth }
                v.append([length, breadth ])
 
                # Insert { breadth, length }
                v.append([breadth, length ])
            else:
                # Insert { length, breadth}
                # because both are equal
                v.append([length, breadth ])
 
    # Stores the count of rectangles
    # in a grid whose area equal to A
    total = 0
 
    # Iterate over all possible
    # values of { length, breadth }
    for it in v:
 
        # Stores total count of ways to
        # select a segment of length it.first
        # on the segment of length M
        num1 = (max(0, M - it[0] + 1))
 
        # Stores total count of ways to
        # select a segment of length it.second
        # on the segment of length N
        num2 = (max(0, N - it[1] + 1))
 
        # Update total
        total += (num1 * num2)
    return total
 
# Drivers Code
if __name__ == '__main__':
 
    # Input
    N, M, A = 2, 2, 2
 
    # Print the result
    print(count_number(N, M, A))
 
# This code is contributed by mohit kumar 29.

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
 
  public class pair 
  { 
    public int first, second; 
    public pair(int first, int second) 
    { 
      this.first = first; 
      this.second = second; 
    } 
  }
 
  // Function to find the count of rectangles
  // in an M * N grid such that the area of
  // the rectangles is equal to A
  static int count_number(int N, int M, int A)
  {
 
    // Stores all possible values of length
    // and breadth whose area equal to A
    List<pair> v = new List<pair>();
 
    // Calculate all divisors of A
    for (int i = 1; i * i <= A; i++)
    {
 
      // If N is divisible by i
      if (N % i == 0)
      {
 
        // Stores length of the rectangle
        int length = i;
 
        // Stores breadth of the rectangle
        int breadth = A / i;
 
        // If length of rectangle is not
        // equal to breadth of rectangle
        if (length != breadth)
        {
 
          v.Add(new pair(length, breadth));
 
          // Insert { breadth, length }
          v.Add(new pair(breadth, length));
        }
        else
        {
 
          // Insert { length, breadth}
          // because both are equal
          v.Add(new pair(length, breadth));
        }
      }
    }
 
    // Stores the count of rectangles
    // in a grid whose area equal to A
    int total = 0;
 
    // Iterate over all possible
    // values of { length, breadth }
    foreach (pair it in v)
    {
 
      // Stores total count of ways to
      // select a segment of length it.first
      // on the segment of length M
      int num1 = (Math.Max(0, M - it.first + 1));
 
      // Stores total count of ways to
      // select a segment of length it.second
      // on the segment of length N
      int num2 = (Math.Max(0, N - it.second + 1));
 
      // Update total
      total += (num1 * num2);
    }
    return total;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    // Input
    int N = 2, M = 2, A = 2;
 
    // Print the result
    Console.Write(count_number(N, M, A) +"\n");
  }
}
 
// This code is contributed by susmitakundugoaldang

<script>
// Javascript program of the above approach
 
class pair
{
    constructor(first,second)
    {
        this.first = first;
        this.second = second;
    }
}
 
function count_number(N,M,A)
{
    // Stores all possible values of length
    // and breadth whose area equal to A
    let v = [];
  
    // Calculate all divisors of A
    for (let i = 1; i * i <= A; i++)
    {
  
        // If N is divisible by i
        if (N % i == 0)
        {
  
            // Stores length of the rectangle
            let length = i;
  
            // Stores breadth of the rectangle
            let breadth = A / i;
  
            // If length of rectangle is not
            // equal to breadth of rectangle
            if (length != breadth)
            {
  
                // Insert { length, breadth }
                v.push(new pair(length, breadth));
  
                // Insert { breadth, length }
                v.push(new pair(breadth, length));
            }
            else
            {
  
                // Insert { length, breadth}
                // because both are equal
                v.push(new pair(length, breadth));
            }
        }
    }
  
    // Stores the count of rectangles
    // in a grid whose area equal to A
    let total = 0;
  
    // Iterate over all possible
    // values of { length, breadth }
    for (let it=0;it< v.length;it++)
    {
  
        // Stores total count of ways to
        // select a segment of length it.first
        // on the segment of length M
        let num1 = (Math.max(0, M - v[it].first + 1));
  
        // Stores total count of ways to
        // select a segment of length it.second
        // on the segment of length N
        let num2 = (Math.max(0, N - v[it].second + 1));
  
        // Update total
        total += (num1 * num2);
    }
    return total;
}
 
// Drivers Code
// Input
let N = 2, M = 2, A = 2;
  
// Print the result
document.write(count_number(N, M, A) +"<br>");
 
 
// This code is contributed by unknown2108
</script>

4

Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(sqrt(N))