Recuento de pares de los primeros N números naturales con un resto de al menos K

Dados dos enteros positivos N y K , la tarea es encontrar el número de pares (a, b) en el rango [1, N] tal que a%b sea al menos K .

Ejemplos:

Entrada: N = 5, K = 2
Salida: 7
Explicación: 
Los siguientes son todos los pares posibles que satisfacen los criterios dados:

1. (2, 3): El valor de 2%3 = 2(>= K).
2. (5, 3): El valor de 5%3 = 2(>= K).
3. (2, 4): El valor de 2%4 = 2(>= K).
4. (3, 4): El valor de 3%4 = 3(>= K).
5. (2, 5): El valor de 2%5 = 2(>= K).
6. (3, 5): El valor de 3%5 = 3(>= K).
7. (4, 5): El valor de 4%5 = 4(>= K).

Por lo tanto, la cuenta total de pares es 7.

Entrada: N = 6, K = 0
Salida: 36

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles (a, b) en el rango [1, N] y si el valor de a%b es al menos K , entonces cuente este par. Después de verificar todos los pares, imprima el total de pares obtenidos.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar iterando sobre el rango [1, N] y fijando el segundo número en el par, es decir, b . Para cada b fijo habrá un período de N/b y cada período se puede combinar con (b – K) elementos. Entonces, habrá un total de (N/b)*(b – K) elementos. Ahora, para los elementos restantes que son N%b , habrá pares máximos (0, n%b – k + 1) . Siga los pasos a continuación para resolver el problema:

• Si el valor de K es 0 , imprima N ² como el número resultante de pares válidos.
• Inicialice la variable, digamos ans como 0 que almacena el conteo resultante de pares.
• Iterar sobre el rango [K + 1, N] usando la variable b y realizar los siguientes pasos:
  • Agregue el valor de (N/b)*(b – K) a la variable ans .
  • Sume el valor del máximo de (N % b – K + 1) o 0 a la variable ans .
• Después de realizar los pasos anteriores, imprima el valor de ans como el conteo de pares resultante.

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 count the number of pairs
// (a, b) such that a%b is at least K
int countTotalPairs(int N, int K)
{
    // Base Case
    if (K == 0) {
        return N * N;
    }
 
    // Stores resultant count of pairs
    int ans = 0;
 
    // Iterate over the range [K + 1, N]
    for (int b = K + 1; b <= N; b++) {
 
        // Find the cycled elements
        ans += (N / b) * (b - K);
 
        // Find the remaining elements
        ans += max(N % b - K + 1, 0);
    }
 
    // Return the resultant possible
    // count of pairs
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5, K = 2;
    cout << countTotalPairs(N, K);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
  // Function to count the number of pairs
  // (a, b) such that a%b is at least K
  public static int countTotalPairs(int N, int K)
  {
 
    // Base case
    if (K == 0) {
      return N * N;
    }
 
    // Stores resultant count of pairs
    int ans = 0;
 
    // Iterate over the range [K + 1, N]
    for (int i = K + 1; i <= N; i++)
    {
 
      // Find the cycled element
      ans += (N / i) * (i - K);
      if ((N % i) - K + 1 > 0)
      {
 
        // Find the remaining element
        ans += (N % i) - K + 1;
      }
    }
 
    // Return the resultant possible
    // count of pairs
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 5, K = 2;
    System.out.println(countTotalPairs(N, K));
  }
}
 
// This code is contributed by maddler.

# Python program for the above approach;
 
# Function to count the number of pairs
# (a, b) such that a%b is at least K
def countTotalPairs(N, K):
    # Base Case
    if (K == 0) :
        return N * N
     
 
    # Stores resultant count of pairs
    ans = 0
 
    # Iterate over the range [K + 1, N]
    for b in range(K + 1, N + 1) :
 
        # Find the cycled elements
        ans += (N // b) * (b - K)
 
        # Find the remaining elements
        ans += max(N % b - K + 1, 0)
     
 
    # Return the resultant possible
    # count of pairs
    return ans
 
 
# Driver Code
 
N = 5
K = 2
print(countTotalPairs(N, K))
 
# This code is contributed by _saurabh_jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count the number of pairs
// (a, b) such that a%b is at least K
static int countTotalPairs(int N, int K)
{
    // Base Case
    if (K == 0) {
        return N * N;
    }
 
    // Stores resultant count of pairs
    int ans = 0;
 
    // Iterate over the range [K + 1, N]
    for (int b = K + 1; b <= N; b++) {
 
        // Find the cycled elements
        ans += (N / b) * (b - K);
 
        // Find the remaining elements
        ans += Math.Max(N % b - K + 1, 0);
    }
 
    // Return the resultant possible
    // count of pairs
    return ans;
}
 
// Driver Code
public static void Main()
{
    int N = 5, K = 2;
    Console.Write(countTotalPairs(N, K));
}
}
 
// This code is contributed by ipg2016107.

<script>
 
        // JavaScript program for the above approach;
 
        // Function to count the number of pairs
        // (a, b) such that a%b is at least K
        function countTotalPairs(N, K) {
            // Base Case
            if (K == 0) {
                return N * N;
            }
 
            // Stores resultant count of pairs
            let ans = 0;
 
            // Iterate over the range [K + 1, N]
            for (let b = K + 1; b <= N; b++) {
 
                // Find the cycled elements
                ans += Math.floor((N / b) * (b - K));
 
                // Find the remaining elements
                ans += Math.max(N % b - K + 1, 0);
            }
 
            // Return the resultant possible
            // count of pairs
            return ans;
        }
 
        // Driver Code
 
        let N = 5, K = 2;
        document.write(countTotalPairs(N, K));
 
   // This code is contributed by Potta Lokesh
    </script>

7

Complejidad temporal: O(N)
Espacio auxiliar: O(1)