Recuento de tripletes ordenados (a, b, c) cuyo producto es como máximo N

Dado un número entero N , la tarea es encontrar el número de tripletes (a, b, c) tales que a <= b <= c y a * b * c <= N.

Ejemplos:

Entrada: N = 5
Salida: 6
Explicación: Los tripletes que siguen las condiciones requeridas son (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5) y (1, 2, 2). Por lo tanto, la cuenta de tripletes de valor es 6. 

Entrada: N = 20
Salida: 40

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

• Dado que a <= b <=c , se puede observar que el valor de a debe estar en el rango [1, N ^1/3 ] .
• De manera similar, para a dado , el valor de b debe estar en el rango [a, (N/a) ^1/2 ] .
• De manera similar, cuando el valor de a y b es fijo, el valor de c debe estar en el rango [b, N/(a*b)] . Por lo tanto, el número de valores posibles de c es el recuento de enteros en el rango [b, N/(a*b)] . Por lo tanto, para cada a y b válidos , el número de valores posibles de c es N/(a*b) – b + 1 .

Por lo tanto, el uso de las observaciones anteriores a continuación es la implementación del enfoque anterior:

// C++ implementation of the above approach
#include <iostream>
using namespace std;
 
// Function to find the count of valid
// triplets (a, b, c) such that the value
// of a * b * c <= N and a <= b <= c
long long validTriplets(int N)
{
    // Stores count of triplets
    long long ans = 0;
 
    // Loop to iterate in the
    // range [1, N^(1/3)]
    for (long long a = 1; a * a * a <= N; a++) {
 
        // Loop to iterate in the
        // range [a, (N/a)^(1/2)]
        for (long long b = a; a * b * b <= N; b++) {
 
            // Add the count of valid
            // values of c for a fixed
            // value of a and b
            ans += N / a / b - b + 1;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5;
    cout << validTriplets(N);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
// Function to find the count of valid
// triplets (a, b, c) such that the value
// of a * b * c <= N and a <= b <= c
static long validTriplets(int N)
{
   
    // Stores count of triplets
    long ans = 0;
 
    // Loop to iterate in the
    // range [1, N^(1/3)]
    for (long a = 1; a * a * a <= N; a++) {
 
        // Loop to iterate in the
        // range [a, (N/a)^(1/2)]
        for (long b = a; a * b * b <= N; b++) {
 
            // Add the count of valid
            // values of c for a fixed
            // value of a and b
            ans += N / a / b - b + 1;
        }
    }
 
    // Return Answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    System.out.print(validTriplets(N));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python implementation of the above approach
 
# Function to find the count of valid
# triplets (a, b, c) such that the value
# of a * b * c <= N and a <= b <= c
def validTriplets(N):
     
    # Stores count of triplets
    ans = 0;
 
    # Loop to iterate in the
    # range [1, N^(1/3)]
    for a in range(1, int(N ** (1 / 3)) + 1):
     
        # Loop to iterate in the
        # range [a, (N/a)^(1/2)]
        b = a;
        while(a * b * b <= N):
            # Add the count of valid
            # values of c for a fixed
            # value of a and b
            ans += N / a / b - b + 1;
            b += 1
     
    # Return Answer
    return int(ans);
 
# Driver Code
N = 5;
 
print(validTriplets(N));
 
# This code is contributed by gfgking

// C# implementation of the above approach
using System;
class GFG {
    // Function to find the count of valid
    // triplets (a, b, c) such that the value
    // of a * b * c <= N and a <= b <= c
    static long validTriplets(int N)
    {
        // Stores count of triplets
        long ans = 0;
 
        // Loop to iterate in the
        // range [1, N^(1/3)]
        for (long a = 1; a * a * a <= N; a++) {
 
            // Loop to iterate in the
            // range [a, (N/a)^(1/2)]
            for (long b = a; a * b * b <= N; b++) {
 
                // Add the count of valid
                // values of c for a fixed
                // value of a and b
                ans += N / a / b - b + 1;
            }
        }
 
        // Return Answer
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 5;
        Console.WriteLine(validTriplets(N));
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript implementation of the above approach
 
// Function to find the count of valid
// triplets (a, b, c) such that the value
// of a * b * c <= N and a <= b <= c
function validTriplets(N)
{
     
    // Stores count of triplets
    let ans = 0;
 
    // Loop to iterate in the
    // range [1, N^(1/3)]
    for(let a = 1; a * a * a <= N; a++)
    {
         
        // Loop to iterate in the
        // range [a, (N/a)^(1/2)]
        for(let b = a; a * b * b <= N; b++)
        {
             
            // Add the count of valid
            // values of c for a fixed
            // value of a and b
            ans += N / a / b - b + 1;
        }
    }
     
    // Return Answer
    return Math.floor(ans);
}
 
// Driver Code
let N = 5;
 
document.write(validTriplets(N));
 
// This code is contributed by Potta Lokesh
 
</script>

6

Complejidad de Tiempo: O(N ^2/3 )
Espacio Auxiliar: O(1)