Dado un entero par positivo N , la tarea es encontrar el número de pares (i, j) del rango [1, N] tal que el producto de i y L 1 sea el mismo que el producto de j y L 2 donde i < j y L 1 y L 2 cualquier número del rango [1, N/2] .
Ejemplos:
Entrada: N = 4
Salida: 2
Explicación:
Los posibles pares que satisfacen los criterios dados son:
- (1, 2): Como 1 < 2, y 1*2 = 2*1 donde L 1 = 2 y L 2 = 1.
- (2, 4): Como 2 < 4 y 2*2 = 4*1 donde L 1 = 2 y L 2 = 1.
Por lo tanto, la cuenta total es 2.
Entrada: N = 6
Salida: 7
Enfoque ingenuo: el problema dado se puede resolver en función de las siguientes observaciones:
Sea i * L 1 = j * L 2 = mcm(i, j) — (1)
⇒ L 1 = mcm(i, j)/ i
= j/mcd(i, j)De manera similar, L 2 = i/mcd(i, j)
Ahora, para que se cumpla la condición, L1 y L2 deben estar en el rango [1, N/2].
Por lo tanto, la idea es generar todos los pares posibles (i, j) en el rango [1, N] y si existe algún par (i, j) tal que el valor de i/mcd(i, j) y j/ mcd(i, j) es menor que N/2 , luego incremente el conteo de pares en 1 . Después de verificar todos los pares, imprima el valor del conteo como resultado.
Complejidad de tiempo: O(N 2 *log N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la función Totient de Euler . Existen los siguientes 2 casos para cualquier par (i, j) :
- Caso 1: Si el par (i, j) se encuentra en el rango [1, N/2] , entonces todos los posibles pares formados satisfarán la condición dada. Por lo tanto, el recuento total de pares viene dado por (z*(z – 1))/2 , donde z = N/2 .
- Caso 2: si todos los pares posibles (i, j) se encuentran en el rango [N/2 + 1, N] con mcd (i, j) mayor que 1 , se cumplen las condiciones dadas.
Siga los pasos a continuación para contar el número total de este tipo de pares:
- Calcule Φ para todos los números menores o iguales a N usando la función Totient de Euler para todos los números menores o iguales a N .
- Para un número j , el número total de pares posibles (i, j) se puede calcular como (j – Φ(j) – 1) .
- Para cada número en el rango [N/2 + 1, N] , cuente los pares de números totales usando la fórmula anterior.
- Después de completar los pasos anteriores, imprima la suma de los valores obtenidos en los dos pasos anteriores como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to compute totient of all
// numbers smaller than or equal to N
void computeTotient(int N, int phi[])
{
// Iterate over the range [2, N]
for (int p = 2; p <= N; p++) {
// If phi[p] is not computed
// already, then p is prime
if (phi[p] == p) {
// Phi of a prime number
// p is (p - 1)
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (int i = 2 * p; i <= N;
i += p) {
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to count the pairs (i, j)
// from the range [1, N], satisfying
// the given condition
void countPairs(int N)
{
// Stores the counts of first and
// second type of pairs respectively
int cnt_type1 = 0, cnt_type2 = 0;
// Count of first type of pairs
int half_N = N / 2;
cnt_type1 = (half_N * (half_N - 1)) / 2;
// Stores the phi or totient values
int phi[N + 1];
for (int i = 1; i <= N; i++) {
phi[i] = i;
}
// Calculate the Phi values
computeTotient(N, phi);
// Iterate over the range
// [N/2 + 1, N]
for (int i = (N / 2) + 1;
i <= N; i++)
// Update the value of
// cnt_type2
cnt_type2 += (i - phi[i] - 1);
// Print the total count
cout << cnt_type1 + cnt_type2;
}
// Driver Code
int main()
{
int N = 6;
countPairs(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to compute totient of all
// numbers smaller than or equal to N
static void computeTotient(int N, int phi[])
{
// Iterate over the range [2, N]
for(int p = 2; p <= N; p++)
{
// If phi[p] is not computed
// already, then p is prime
if (phi[p] == p)
{
// Phi of a prime number
// p is (p - 1)
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for(int i = 2 * p; i <= N; i += p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to count the pairs (i, j)
// from the range [1, N], satisfying
// the given condition
static void countPairs(int N)
{
// Stores the counts of first and
// second type of pairs respectively
int cnt_type1 = 0, cnt_type2 = 0;
// Count of first type of pairs
int half_N = N / 2;
cnt_type1 = (half_N * (half_N - 1)) / 2;
// Stores the phi or totient values
int []phi = new int[N + 1];
for(int i = 1; i <= N; i++)
{
phi[i] = i;
}
// Calculate the Phi values
computeTotient(N, phi);
// Iterate over the range
// [N/2 + 1, N]
for(int i = (N / 2) + 1;
i <= N; i++)
// Update the value of
// cnt_type2
cnt_type2 += (i - phi[i] - 1);
// Print the total count
System.out.print(cnt_type1 + cnt_type2);
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
countPairs(N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to compute totient of all # numbers smaller than or equal to N def computeTotient(N, phi): # Iterate over the range [2, N] for p in range(2, N + 1): # If phi[p] is not computed # already then p is prime if phi[p] == p: # Phi of a prime number # p is (p - 1) phi[p] = p - 1 # Update phi values of # all multiples of p for i in range(2 * p, N + 1, p): # Add contribution of p # to its multiple i by # multiplying with (1 - 1/p) phi[i] = (phi[i] // p) * (p - 1) # Function to count the pairs (i, j) # from the range [1, N], satisfying # the given condition def countPairs(N): # Stores the counts of first and # second type of pairs respectively cnt_type1 = 0 cnt_type2 = 0 # Count of first type of pairs half_N = N // 2 cnt_type1 = (half_N * (half_N - 1)) // 2 # Count of second type of pairs # Stores the phi or totient values phi = [0 for i in range(N + 1)] for i in range(1, N + 1): phi[i] = i # Calculate the Phi values computeTotient(N, phi) # Iterate over the range # [N/2 + 1, N] for i in range((N // 2) + 1, N + 1): # Update the value of # cnt_type2 cnt_type2 += (i - phi[i] - 1) # Print the total count print(cnt_type1 + cnt_type2) # Driver Code if __name__ == '__main__': N = 6 countPairs(N) # This code is contributed by kundudinesh007.
C#
// C# program for the above approach
using System;
class GFG {
// Function to compute totient of all
// numbers smaller than or equal to N
static void computeTotient(int N, int[] phi)
{
// Iterate over the range [2, N]
for (int p = 2; p <= N; p++) {
// If phi[p] is not computed
// already, then p is prime
if (phi[p] == p) {
// Phi of a prime number
// p is (p - 1)
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (int i = 2 * p; i <= N; i += p) {
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to count the pairs (i, j)
// from the range [1, N], satisfying
// the given condition
static void countPairs(int N)
{
// Stores the counts of first and
// second type of pairs respectively
int cnt_type1 = 0, cnt_type2 = 0;
// Count of first type of pairs
int half_N = N / 2;
cnt_type1 = (half_N * (half_N - 1)) / 2;
// Stores the phi or totient values
int[] phi = new int[N + 1];
for (int i = 1; i <= N; i++) {
phi[i] = i;
}
// Calculate the Phi values
computeTotient(N, phi);
// Iterate over the range
// [N/2 + 1, N]
for (int i = (N / 2) + 1; i <= N; i++)
// Update the value of
// cnt_type2
cnt_type2 += (i - phi[i] - 1);
// Print the total count
Console.Write(cnt_type1 + cnt_type2);
}
// Driver Code
public static void Main()
{
int N = 6;
countPairs(N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program implementation
// of the approach
// Function to compute totient of all
// numbers smaller than or equal to N
function computeTotient(N, phi)
{
// Iterate over the range [2, N]
for(let p = 2; p <= N; p++)
{
// If phi[p] is not computed
// already, then p is prime
if (phi[p] == p)
{
// Phi of a prime number
// p is (p - 1)
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for(let i = 2 * p; i <= N; i += p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to count the pairs (i, j)
// from the range [1, N], satisfying
// the given condition
function countPairs(N)
{
// Stores the counts of first and
// second type of pairs respectively
let cnt_type1 = 0, cnt_type2 = 0;
// Count of first type of pairs
let half_N = N / 2;
cnt_type1 = (half_N * (half_N - 1)) / 2;
// Stores the phi or totient values
let phi = Array.from({length: N+1}, (_, i) => 0);
for(let i = 1; i <= N; i++)
{
phi[i] = i;
}
// Calculate the Phi values
computeTotient(N, phi);
// Iterate over the range
// [N/2 + 1, N]
for(let i = (N / 2) + 1;
i <= N; i++)
// Update the value of
// cnt_type2
cnt_type2 += (i - phi[i] - 1);
// Print the total count
document.write(cnt_type1 + cnt_type2);
}
// Driver Code
let N = 6;
countPairs(N);
// This code is contributed by souravghosh0416.
</script>
Producción:
7
Complejidad de Tiempo: O(N*log(log(N)))
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA