Dada una array arr[] que consta de N enteros, la tarea para cada i -ésimo elemento de la array es encontrar el número de pares no coprimos del rango [1, arr[i]] .
Ejemplos:
Entrada: N = 2, arr[] = {3, 4}
Salida: 2 4
Explicación:
- Todos los pares no coprimos del rango [1, 3] son (2, 2) y (3, 3).
- Todos los pares no coprimos del rango [1, 4] son (2, 2), (2, 4), (3, 3) y (4, 4).
Entrada: N = 3, arr[] = {5, 10, 20}
Salida: 5 23 82
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre cada i -ésimo elemento de la array y luego, generar todos los pares posibles del rango [1, arr[i]] , y para cada par, verificar si es no co -primo, es decir, el mcd del par es mayor que 1 o no.
Siga los pasos a continuación para resolver este problema:
- Itere sobre el rango [0, N – 1] usando una variable, digamos i, y realice los siguientes pasos:
- Inicialice las variables lastEle como arr[i] y cuente como 0 para almacenar el último valor del rango actual y el número de pares coprimos respectivamente.
- Itere sobre cada par del rango [1, arr[i]] usando las variables x e y y haga lo siguiente :
- Si GCD(x, y) es mayor que 1 , entonces el incremento cuenta en 1 .
- Finalmente, imprima el conteo como la respuesta.
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;
// Recursive function to
// return gcd of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to count the number of
// non co-prime pairs for each query
void countPairs(int* arr, int N)
{
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count of
// non co-prime pairs
int count = 0;
// Iterate over the range [1, x]
for (int x = 1; x <= arr[i]; x++) {
// Iterate over the range [x, y]
for (int y = x; y <= arr[i]; y++) {
// If gcd of current pair
// is greater than 1
if (gcd(x, y) > 1)
count++;
}
}
cout << count << " ";
}
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Recursive function to
// return gcd of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to count the number of
// non co-prime pairs for each query
static void countPairs(int[] arr, int N)
{
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Stores the count of
// non co-prime pairs
int count = 0;
// Iterate over the range [1, x]
for(int x = 1; x <= arr[i]; x++)
{
// Iterate over the range [x, y]
for(int y = x; y <= arr[i]; y++)
{
// If gcd of current pair
// is greater than 1
if (gcd(x, y) > 1)
count++;
}
}
System.out.print(count + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by subhammahato348
Python3
# Python3 program for the above approach # Recursive program to # return gcd of two numbers def gcd(a, b): if b == 0: return a return gcd(b, a % b) # Function to count the number of # non co-prime pairs for each query def countPairs(arr, N): # Traverse the array arr[] for i in range(0, N): # Stores the count of # non co-prime pairs count = 0 # Iterate over the range [1,x] for x in range(1, arr[i] + 1): # Iterate over the range [x,y] for y in range(x, arr[i] + 1): # If gcd of current pair # is greater than 1 if gcd(x, y) > 1: count += 1 print(count, end = " ") # Driver code if __name__ == '__main__': # Given Input arr = [ 5, 10, 20 ] N = len(arr) # Function Call countPairs(arr, N) # This code is contributed by MuskanKalra1
C#
// C# program for the above approach
using System;
class GFG{
// Recursive function to
// return gcd of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to count the number of
// non co-prime pairs for each query
static void countPairs(int[] arr, int N)
{
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Stores the count of
// non co-prime pairs
int count = 0;
// Iterate over the range [1, x]
for(int x = 1; x <= arr[i]; x++)
{
// Iterate over the range [x, y]
for(int y = x; y <= arr[i]; y++)
{
// If gcd of current pair
// is greater than 1
if (gcd(x, y) > 1)
count++;
}
}
Console.Write(count + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given Input
int []arr = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Recursive function to
// return gcd of two numbers
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to count the number of
// non co-prime pairs for each query
function countPairs(arr, N)
{
// Traverse the array arr[]
for(var i = 0; i < N; i++)
{
// Stores the count of
// non co-prime pairs
var count = 0;
// Iterate over the range [1, x]
for(var x = 1; x <= arr[i]; x++)
{
// Iterate over the range [x, y]
for(var y = x; y <= arr[i]; y++)
{
// If gcd of current pair
// is greater than 1
if (gcd(x, y) > 1)
count++;
}
}
document.write(count + " ");
}
}
// Driver Code
// Given Input
var arr = [ 5, 10, 20 ];
var N = 3;
// Function Call
countPairs(arr, N);
// This code is contributed by shivanisinghss2110
</script>
Producción
5 23 82
Complejidad temporal: O(N*M 2 *log(M)), donde M es el elemento máximo de la array.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la función totient de Euler y la array de suma de prefijos . Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays, digamos phi[] y ans[] como 0 , donde el i -ésimo elemento de la array representa el conteo de enteros coprimos con i y el conteo de pares no coprimos formados a partir del rango [1, arr[ i]].
- Iterar sobre el rango [1, MAX] usando una variable, digamos i, y asignar i a phi[i].
- Itere sobre el rango [2, MAX] usando una variable, digamos i, y realice los siguientes pasos:
- Si phi[i] = i, itere sobre el rango [i, MAX] usando una variable j y realice los siguientes pasos:
- Decremente phi[j] / i de phi[j] y luego incremente j por i .
- Si phi[i] = i, itere sobre el rango [i, MAX] usando una variable j y realice los siguientes pasos:
- Itere sobre el rango [1, MAX] usando una variable, digamos i, y realice los siguientes pasos:
- Actualice ans[i] a ans[i – 1] + (i – phi[i]).
- Finalmente, después de completar los pasos anteriores, imprima la array ans[] .
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;
const int MAX = 1005;
// Auxiliary function to pre-compute
// the answer for each array
void preCalculate(vector<int>& phi,
vector<int>& ans)
{
phi[0] = 0;
phi[1] = 1;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++)
phi[i] = i;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++) {
// If the number is prime
if (phi[i] == i) {
for (int j = i; j <= MAX; j += i)
// Subtract the number of
// pairs which has i as one
// of their factors
phi[j] -= (phi[j] / i);
}
}
// Iterate over the range [1, MAX]
for (int i = 1; i <= MAX; i++)
ans[i] = ans[i - 1] + (i - phi[i]);
}
// Function to count the number of
// non co-prime pairs for each query
void countPairs(int* arr, int N)
{
// The i-th element stores
// the count of element that
// are co-prime with i
vector<int> phi(1e5, 0);
// Stores the resulting array
vector<int> ans(1e5, 0);
// Function Call
preCalculate(phi, ans);
// Traverse the array arr[]
for (int i = 0; i < N; ++i) {
cout << ans[arr[i]] << " ";
}
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
static int MAX = 1005;
// Auxiliary function to pre-compute
// the answer for each array
static void preCalculate(int[] phi,
int[] ans)
{
phi[0] = 0;
phi[1] = 1;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++)
phi[i] = i;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++) {
// If the number is prime
if (phi[i] == i) {
for (int j = i; j <= MAX; j += i)
// Subtract the number of
// pairs which has i as one
// of their factors
phi[j] -= (phi[j] / i);
}
}
// Iterate over the range [1, MAX]
for (int i = 1; i <= MAX; i++)
ans[i] = ans[i - 1] + (i - phi[i]);
}
// Function to count the number of
// non co-prime pairs for each query
static void countPairs(int[] arr, int N)
{
// The i-th element stores
// the count of element that
// are co-prime with i
int[] phi = new int[100000];
Arrays.fill(phi, 0);
// Stores the resulting array
int[] ans = new int[100000];
Arrays.fill(ans, 0);
// Function Call
preCalculate(phi, ans);
// Traverse the array arr[]
for (int i = 0; i < N; ++i) {
System.out.print(ans[arr[i]] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by code_hunt.
Python3
MAX = 1005; def preCalculate(phi,ans): phi[0] = 0 phi[1] = 1 # Iterate over the range [1, MAX] for i in range(2, MAX+1): phi[i] = i # Iterate over the range [1, MAX] for i in range(2, MAX+1): if (phi[i] == i): for j in range(i, MAX+1, i): # Subtract the number of # pairs which has i as one # of their factors phi[j] -= (phi[j] // i); # Iterate over the range [1, MAX] for i in range(1, MAX+1): ans[i] = ans[i - 1] + (i - phi[i]); # Function to count the number of # non co-prime pairs for each query def countPairs(arr, N): # The i-th element stores # the count of element that # are co-prime with i phi = [0 for i in range(100001)] # Stores the resulting array ans = [0 for i in range(100001)] # Function Call preCalculate(phi, ans); # Traverse the array arr[] for i in range(N): print(ans[arr[i]],end=' '); # Given Input arr= [5, 10, 20] N = 3; # Function Call countPairs(arr, N); # This code is contributed by rutvik_56.
C#
// C# program for the above approach
using System;
class GFG{
static int MAX = 1005;
// Auxiliary function to pre-compute
// the answer for each array
static void preCalculate(int[] phi,
int[] ans)
{
phi[0] = 0;
phi[1] = 1;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++)
phi[i] = i;
// Iterate over the range [1, MAX]
for (int i = 2; i <= MAX; i++) {
// If the number is prime
if (phi[i] == i) {
for (int j = i; j <= MAX; j += i)
// Subtract the number of
// pairs which has i as one
// of their factors
phi[j] -= (phi[j] / i);
}
}
// Iterate over the range [1, MAX]
for (int i = 1; i <= MAX; i++)
ans[i] = ans[i - 1] + (i - phi[i]);
}
// Function to count the number of
// non co-prime pairs for each query
static void countPairs(int[] arr, int N)
{
// The i-th element stores
// the count of element that
// are co-prime with i
int[] phi = new int[100000];
Array.Clear(phi, 0, 100000);
// Stores the resulting array
int[] ans = new int[100000];
Array.Clear(ans, 0, 100000);
// Function Call
preCalculate(phi, ans);
// Traverse the array arr[]
for (int i = 0; i < N; ++i) {
Console.Write(ans[arr[i]] + " ");
}
}
// Driver Code
public static void Main()
{
// Given Input
int[] arr = { 5, 10, 20 };
int N = 3;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program for the above approach
const MAX = 1005;
// Auxiliary function to pre-compute
// the answer for each array
function preCalculate(phi, ans) {
phi[0] = 0;
phi[1] = 1;
// Iterate over the range [1, MAX]
for (let i = 2; i <= MAX; i++) phi[i] = i;
// Iterate over the range [1, MAX]
for (let i = 2; i <= MAX; i++) {
// If the number is prime
if (phi[i] == i) {
for (let j = i; j <= MAX; j += i)
// Subtract the number of
// pairs which has i as one
// of their factors
phi[j] -= Math.floor(phi[j] / i);
}
}
// Iterate over the range [1, MAX]
for (let i = 1; i <= MAX; i++)
ans[i] = ans[i - 1] + (i - phi[i]);
}
// Function to count the number of
// non co-prime pairs for each query
function countPairs(arr, N) {
// The i-th element stores
// the count of element that
// are co-prime with i
let phi = new Array(1e5).fill(0);
// Stores the resulting array
let ans = new Array(1e5).fill(0);
// Function Call
preCalculate(phi, ans);
// Traverse the array arr[]
for (let i = 0; i < N; ++i) {
document.write(ans[arr[i]] + " ");
}
}
// Driver Code
// Given Input
let arr = [5, 10, 20];
let N = 3;
// Function Call
countPairs(arr, N);
</script>
Producción
5 23 82
Complejidad temporal: O(N+ M*log(N)), donde M es el elemento máximo del arreglo.
Espacio Auxiliar: O(M+N)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA