Dado un número N , la tarea es encontrar el número de pares (a, b) en el rango [1, N] tal que su MCM no sea igual a su producto, es decir, MCM(a, b) != (a* b) y (b > a) . Puede haber múltiples consultas para responder.
Ejemplos:
Entrada: Q[] = {5}
Salida: 1
Explicación:
El par del 1 al 5 es (2, 4)
Entrada: Q[] = {5, 7}
Salida: 1, 4
Explicación:
El par del 1 al 5 es (2, 4)
Los pares del 1 al 7 son (2, 4), (2, 6), (3, 6), (4, 6)
Planteamiento: La idea es utilizar la Función Totient de Euler .
1. Encuentra el número total de pares que se pueden formar usando números del 1 al N. El número de pares formados es igual a ( N * (N – 1)) / 2 .
2. Para cada entero i ≤ N, utilice la función Totient de Euler para encontrar todos los pares coprimos con i y almacenarlos en la array.
Ejemplo:
arr[10] = 10 * (1-1/2) * (1-1/5)
= 4
3.
4. Ahora construya la tabla de suma de prefijos que almacena la suma de todos los phi(i) para todos los i entre 1 y N. Usando esto, podemos responder cada consulta en O(1) tiempo.
5. Finalmente, la respuesta para cualquier i ≤ N viene dada por la diferencia entre el número total de pares formados y pref[i].
A continuación se muestra la implementación del enfoque dado:
C++
// C++ program to find the count of pairs
// from 1 to N such that their LCM
// is not equal to their product
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// To store Euler's Totient Function
int phi[N];
// To store prefix sum table
int pref[N];
// Compute Totients of all numbers
// smaller than or equal to N
void precompute()
{
// Make phi[1]=0 since 1 cannot form any pair
phi[1] = 0;
// Initialise all remaining phi[] with i
for (int i = 2; i < N; i++)
phi[i] = i;
// Compute remaining phi
for (int p = 2; p < N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// phi of prime number is p-1
phi[p] = p - 1;
// Update phi of all multiples of p
for (int i = 2 * p; i < N; i += p) {
// Add the contribution of p
// to its multiple i by multiplying
// it with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to store prefix sum table
void prefix()
{
// Prefix Sum of all Euler's Totient Values
for (int i = 1; i < N; i++)
pref[i] = pref[i - 1] + phi[i];
}
void find_pairs(int n)
{
// Total number of pairs that can be formed
int total = (n * (n - 1)) / 2;
int ans = total - pref[n];
cout << "Number of pairs from 1 to "
<< n << " are " << ans << endl;
}
// Driver Code
int main()
{
// Function call to compute all phi
precompute();
// Function call to store all prefix sum
prefix();
int q[] = { 5, 7 };
int n = sizeof(q) / sizeof(q[0]);
for (int i = 0; i < n; i++) {
find_pairs(q[i]);
}
return 0;
}
Java
// Java program to find the count of pairs
// from 1 to N such that their LCM
// is not equal to their product
class GFG{
static final int N = 100005;
// To store Euler's Totient Function
static int []phi = new int[N];
// To store prefix sum table
static int []pref = new int[N];
// Compute Totients of all numbers
// smaller than or equal to N
static void precompute()
{
// Make phi[1] = 0 since 1 cannot form any pair
phi[1] = 0;
// Initialise all remaining phi[] with i
for (int i = 2; i < N; i++)
phi[i] = i;
// Compute remaining phi
for (int p = 2; p < N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// phi of prime number is p-1
phi[p] = p - 1;
// Update phi of all multiples of p
for (int i = 2 * p; i < N; i += p) {
// Add the contribution of p
// to its multiple i by multiplying
// it with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to store prefix sum table
static void prefix()
{
// Prefix Sum of all Euler's Totient Values
for (int i = 1; i < N; i++)
pref[i] = pref[i - 1] + phi[i];
}
static void find_pairs(int n)
{
// Total number of pairs that can be formed
int total = (n * (n - 1)) / 2;
int ans = total - pref[n];
System.out.print("Number of pairs from 1 to "
+ n + " are " + ans +"\n");
}
// Driver Code
public static void main(String[] args)
{
// Function call to compute all phi
precompute();
// Function call to store all prefix sum
prefix();
int q[] = { 5, 7 };
int n = q.length;
for (int i = 0; i < n; i++) {
find_pairs(q[i]);
}
}
}
// This code contributed by Rajput-Ji
Python3
# Python 3 program to find the count of pairs
# from 1 to N such that their LCM
# is not equal to their product
N = 100005
# To store Euler's Totient Function
phi = [0 for i in range(N)]
# To store prefix sum table
pref = [0 for i in range(N)]
# Compute Totients of all numbers
# smaller than or equal to N
def precompute():
# Make phi[1]=0 since 1 cannot form any pair
phi[1] = 0
# Initialise all remaining phi[] with i
for i in range(2, N, 1):
phi[i] = i
# Compute remaining phi
for p in range(2,N):
# If phi[p] is not computed already,
# then number p is prime
if (phi[p] == p):
# phi of prime number is p-1
phi[p] = p - 1
# Update phi of all multiples of p
for i in range(2*p, N, p):
# Add the contribution of p
# to its multiple i by multiplying
# it with (1 - 1/p)
phi[i] = (phi[i] // p) * (p - 1)
# Function to store prefix sum table
def prefix():
# Prefix Sum of all Euler's Totient Values
for i in range(1, N, 1):
pref[i] = pref[i - 1] + phi[i]
def find_pairs(n):
# Total number of pairs that can be formed
total = (n * (n - 1)) // 2
ans = total - pref[n]
print("Number of pairs from 1 to",n,"are",ans)
# Driver Code
if __name__ == '__main__':
# Function call to compute all phi
precompute()
# Function call to store all prefix sum
prefix()
q = [5, 7]
n = len(q)
for i in range(n):
find_pairs(q[i])
# This code is contributed by Surendra_Gangwar
C#
// C# program to find the count of pairs
// from 1 to N such that their LCM
// is not equal to their product
using System;
class GFG{
static readonly int N = 100005;
// To store Euler's Totient Function
static int []phi = new int[N];
// To store prefix sum table
static int []pref = new int[N];
// Compute Totients of all numbers
// smaller than or equal to N
static void precompute()
{
// Make phi[1] = 0 since 1
// cannot form any pair
phi[1] = 0;
// Initialise all remaining
// phi[] with i
for(int i = 2; i < N; i++)
phi[i] = i;
// Compute remaining phi
for(int p = 2; p < N; p++)
{
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p)
{
// phi of prime number is p-1
phi[p] = p - 1;
// Update phi of all multiples of p
for(int i = 2 * p; i < N; i += p)
{
// Add the contribution of p
// to its multiple i by multiplying
// it with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to store prefix sum table
static void prefix()
{
// Prefix Sum of all
// Euler's Totient Values
for(int i = 1; i < N; i++)
pref[i] = pref[i - 1] + phi[i];
}
static void find_pairs(int n)
{
// Total number of pairs
// that can be formed
int total = (n * (n - 1)) / 2;
int ans = total - pref[n];
Console.Write("Number of pairs from 1 to " +
n + " are " + ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Function call to compute all phi
precompute();
// Function call to store
// all prefix sum
prefix();
int []q = {5, 7};
int n = q.Length;
for(int i = 0; i < n; i++)
{
find_pairs(q[i]);
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find the count of pairs
// from 1 to N such that their LCM
// is not equal to their product
var N = 100005;
// To store Euler's Totient Function
var phi = Array(N).fill(0);
// To store prefix sum table
var pref = Array(N).fill(0);
// Compute Totients of all numbers
// smaller than or equal to N
function precompute() {
// Make phi[1] = 0 since 1 cannot form any pair
phi[1] = 0;
// Initialise all remaining phi with i
for (i = 2; i < N; i++)
phi[i] = i;
// Compute remaining phi
for (p = 2; p < N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// phi of prime number is p-1
phi[p] = p - 1;
// Update phi of all multiples of p
for (i = 2 * p; i < N; i += p) {
// Add the contribution of p
// to its multiple i by multiplying
// it with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Function to store prefix sum table
function prefix() {
// Prefix Sum of all Euler's Totient Values
for (i = 1; i < N; i++)
pref[i] = pref[i - 1] + phi[i];
}
function find_pairs(n) {
// Total number of pairs that can be formed
var total = (n * (n - 1)) / 2;
var ans = total - pref[n];
document.write("Number of pairs from 1 to " + n + " are " + ans + "<br/>");
}
// Driver Code
// Function call to compute all phi
precompute();
// Function call to store all prefix sum
prefix();
var q = [ 5, 7 ];
var n = q.length;
for (i = 0; i < n; i++) {
find_pairs(q[i]);
}
// This code contributed by Rajput-Ji
</script>
Producción:
Number of pairs from 1 to 5 are 1 Number of pairs from 1 to 7 are 4
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por cherry0697 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA