Recuento de pares en el rango [P, Q] con números como múltiplos de R y su producto se encuentra en el rango [P*Q/4, P*Q]

Dados 3 enteros positivos P , Q y R , la tarea es encontrar el número de pares tales que ambos elementos estén en el rango [P, Q] y los números deben ser múltiplos de R , y el producto de los números debe ser en el rango [P × Q / 4, P × Q] . Si no existe tal par, imprima -1.

Ejemplos:

Entrada: P = 14, Q = 30, R = 5
Salida: 15 20
              15 25
Explicación:  
Múltiplos de R entre P y Q son {15, 20, 25, 30}.
P × Q = 420 y P × Q / 4 = 105
Entonces los pares que satisfacen las condiciones anteriores son 15, 20 y 15, 25. 

Entrada: P = 10, Q = 20, R = 7
Salida: 7 14

Enfoque: Para resolver este problema primero, encuentra el rango mínimo y máximo hasta los pares que pueden existir y luego encuentra los pares que satisfacen las condiciones anteriores. Siga los pasos a continuación para resolver el problema:

• Inicialice el vector , digamos, v para almacenar todo el número que está en el rango [P, Q] y es un múltiplo de R y un vector de pares , digamos, ans para almacenar los pares que siguen las condiciones mencionadas anteriormente.
• Iterar en el rango [P, Q] usando la variable i y verificar si i es divisible por R , luego insertar i en el vector v .
• Iterar en el rango [0, v.size()-1] usando la variable i y realizar los siguientes pasos:
  • Iterar en el rango [i+1, v.size()-1] usando la variable j y comprobar si v[j] * v[i] <= P * Q y v[j] * v[i] >= P * Q/4 luego inserte el par en ans .
• Si ans.size() es igual a 0 , imprima -1.
• De lo contrario, imprima los pares en ans .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of
// pairs such that both the elements
// are in the range [P, Q] and the
// numbers should be multiple of R,
// and the product of numbers should
// lie in the range [P*Q/4, P*Q]
void findPairs(int p, int q, int r)
{
    // Store multiple of r
    // in range of [P, Q]
    vector<int> v;
 
    // Iterate in the range [p, q]
    for (int i = p; i <= q; i++) {
        if (i % r == 0) {
            v.push_back(i);
        }
    }
 
    // Vector to store pair of answer
    vector<pair<int, int> > ans;
 
    // Iterate through the vector v
    for (int i = 0; i < v.size(); i++) {
 
        // Iterate in the range [i+1, v.size()-1]
        for (int j = i + 1; j < v.size(); j++) {
 
            // If pair follow this condition
            // insert the pair in vector ans
            if (v[i] * v[j] >= p * q / 4
                && v[i] * v[j] <= p * q) {
                ans.push_back({ v[i], v[j] });
            }
        }
    }
 
    // If no pair satisfy the conditions, print -1
    if (ans.size() == 0) {
        cout << -1 << endl;
    }
    else {
 
        // Print the pairs
        // which satisfy the given condition
        for (int i = 0; i < ans.size(); i++) {
 
            cout << ans[i].first << " "
                 << ans[i].second << endl;
        }
    }
}
 
// Driver Code
int main()
{
 
    // Given Input
    int p = 14, q = 30, r = 5;
 
    // Function Call
    findPairs(p, q, r);
    return 0;
}

//Java program for above approach
import java.awt.*;
import java.util.*;
class GFG{
    static class pair< T, V>{
        T first;
        V second;
    }
 
    // Function to find the number of
    // pairs such that both the elements
    // are in the range [P, Q] and the
    // numbers should be multiple of R,
    // and the product of numbers should
    // lie in the range [P*Q/4, P*Q]
    static void findPairs(int p, int q, int r)
    {
       
        // Store multiple of r
        // in range of [P, Q]
        ArrayList<Integer> v = new ArrayList<>();
 
        // Iterate in the range [p, q]
        for (int i = p; i <= q; i++) {
            if (i % r == 0) {
                v.add(i);
            }
        }
 
        // Vector to store pair of answer
        ArrayList<pair<Integer, Integer> > ans = new ArrayList<>();
 
        // Iterate through the vector v
        for (int i = 0; i < v.size(); i++) {
 
            // Iterate in the range [i+1, v.size()-1]
            for (int j = i + 1; j < v.size(); j++) {
 
                // If pair follow this condition
                // insert the pair in vector ans
                if (v.get(i) * v.get(j) >= p * q / 4
                        && v.get(i) * v.get(j) <= p * q) {
                    pair<Integer,Integer> x = new pair<>();
                    x.first = v.get(i);
                    x.second = v.get(j);
                    ans.add(x);
                }
            }
        }
 
        // If no pair satisfy the conditions, print -1
        if (ans.size() == 0) {
            System.out.println(-1);
        }
        else {
 
            // Print the pairs
            // which satisfy the given condition
            for (int i = 0; i < ans.size(); i++) {
                System.out.println(ans.get(i).first +
                        " " + ans.get(i).second);
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
       
        // Given Input
        int p = 14, q = 30, r = 5;
 
        // Function Call
        findPairs(p, q, r);
    }
}
 
// This code is contributed by hritikrommie.

# Python3 program for the above approach
 
# Function to find the number of
# pairs such that both the elements
# are in the range [P, Q] and the
# numbers should be multiple of R,
# and the product of numbers should
# lie in the range [P*Q/4, P*Q]
def findPairs(p, q, r):
     
    # Store multiple of r
    # in range of [P, Q]
    v = []
 
    # Iterate in the range [p, q]
    for i in range(p, q + 1):
        if (i % r == 0):
            v.append(i)
 
    # Vector to store pair of answer
    ans = []
  
    # Iterate through the vector v
    for i in range(len(v)):
         
        # Iterate in the range [i+1, v.size()-1]
        for j in range(i + 1, len(v)):
             
            # If pair follow this condition
            # insert the pair in vector ans
            if (v[i] * v[j] >= p * q // 4 and
                v[i] * v[j] <= p * q):
                ans.append([v[i], v[j]])
 
    # If no pair satisfy the conditions, pr-1
    if (len(ans) == 0):
        print (-1)
    else:
         
        # Print the pairs
        # which satisfy the given condition
        for i in range(len(ans)):
            print(ans[i][0], ans[i][1])
 
# Driver Code
if __name__ == '__main__':
 
    # Given Input
    p = 14
    q = 30
    r = 5
 
    # Function Call
    findPairs(p, q, r)
     
# This code is contributed by mohit kumar 29

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the number of
// pairs such that both the elements
// are in the range [P, Q] and the
// numbers should be multiple of R,
// and the product of numbers should
// lie in the range [P*Q/4, P*Q]
static void findPairs(int p, int q, int r)
{
    // Store multiple of r
    // in range of [P, Q]
    List<int> v = new List<int>();
 
    // Iterate in the range [p, q]
    for (int i = p; i <= q; i++) {
        if (i % r == 0) {
            v.Add(i);
        }
    }
 
    // Vector to store pair of answer
    List<List<int>> ans = new List<List<int>>();
 
    // Iterate through the vector v
    for(int i = 0; i < v.Count; i++) {
 
        // Iterate in the range [i+1, v.size()-1]
        for (int j = i + 1; j < v.Count; j++) {
 
            // If pair follow this condition
            // insert the pair in vector ans
            if (v[i] * v[j] >= p * q / 4
                && v[i] * v[j] <= p * q) {
                List<int> temp = new List<int>();
                temp.Add(v[i]);
                temp.Add(v[j]);
                ans.Add(temp);
            }
        }
    }
 
    // If no pair satisfy the conditions, print -1
    if (ans.Count == 0) {
        Console.Write(-1);
    }
    else {
          
         foreach (List<int> subList in ans)
        {
            foreach (int item in subList)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
        // Print the pairs
        // which satisfy the given condition
    }
}
 
// Driver Code
public static void Main()
{
 
    // Given Input
    int p = 14, q = 30, r = 5;
 
    // Function Call
    findPairs(p, q, r);
 
}
 
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript program for the above approach
 
 
// Function to find the number of
// pairs such that both the elements
// are in the range [P, Q] and the
// numbers should be multiple of R,
// and the product of numbers should
// lie in the range [P*Q/4, P*Q]
function findPairs(p, q, r) {
    // Store multiple of r
    // in range of [P, Q]
    let v = [];
 
    // Iterate in the range [p, q]
    for (let i = p; i <= q; i++) {
        if (i % r == 0) {
            v.push(i);
        }
    }
 
    // Vector to store pair of answer
    let ans = [];
 
    // Iterate through the vector v
    for (let i = 0; i < v.length; i++) {
 
        // Iterate in the range [i+1, v.size()-1]
        for (let j = i + 1; j < v.length; j++) {
 
            // If pair follow this condition
            // insert the pair in vector ans
            if (v[i] * v[j] >= p * q / 4
                && v[i] * v[j] <= p * q) {
                ans.push([v[i], v[j]]);
            }
        }
    }
 
    // If no pair satisfy the conditions, print -1
    if (ans.length == 0) {
        document.write(-1 + "<br>");
    }
    else {
 
        // Print the pairs
        // which satisfy the given condition
        for (let i = 0; i < ans.length; i++) {
 
            document.write(ans[i][0] + " "
                + ans[i][1] + "<br>");
        }
    }
}
 
// Driver Code
 
// Given Input
let p = 14, q = 30, r = 5;
 
// Function Call
findPairs(p, q, r);
 
// This code is contributed by _saurabh_jaiswal.
</script>

15 20
15 25

Complejidad Temporal: O(N ² ), donde N es Q – P + 1.
Espacio Auxiliar: O(N)