Dada una array arr[] de N enteros y Q consultas de la forma (l, r) . La tarea es encontrar el número de pares distintos de enteros coprimos para cada consulta de modo que todos los enteros en el rango de índice [l, r] sean divisibles por el producto de los enteros coprimos.
Ejemplos:
Entrada: arr[] = {1, 2, 2, 4, 5}, consultas[] = {{2, 3}, {2, 4}, {3, 4}, {4, 4}, {4, 5}}
Salida: 3 3 3 5 1
Explicación: Para la primera consulta [2, 3], el subarreglo es {2, 2}.
Los pares de coprimos que dividen todos los enteros en el subarreglo son {1, 1}, {1, 2} y {2, 1}.
Para la segunda consulta [2, 4], el subarreglo es {2, 2, 4}.
Los pares de coprimos que dividen todos los enteros son {1, 1}, {1, 2} y {2, 1}.
Del mismo modo, proceda para las consultas posteriores.Entrada: arr[] = {20, 10, 15}, consultas[] = {{2, 3}, {1, 3}, {1, 2}}
Salida: 3 3 9
Enfoque: el problema dado se puede resolver de manera óptima con la ayuda de una tabla dispersa . El enfoque se basa en el hecho de que solo los factores primos del GCD de un subarreglo pueden dividir todos sus elementos. Por lo tanto, los factores primos de MCD contribuyen al recuento de pares. El GCD de los rangos se puede calcular de manera óptima utilizando una tabla dispersa. A continuación se detallan los pasos a seguir:
- Cree una tabla dispersa para encontrar los elementos GCD en el rango [L, R] en un tiempo óptimo en varias consultas.
- Itere a través de la array de consulta y para cada consulta, realice lo siguiente:
- Encuentre el GCD de elementos en el rango [L, R] para la consulta actual.
- El problema ahora se reduce a encontrar el número de pares coprimos en el rango [1, GCD] que tienen su producto como GCD , lo que se puede hacer usando el algoritmo discutido aquí .
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;
#define MAXN 200001
int table[1001][1001];
// Function to build sparse table
void buildSparseTable(vector<int> arr, int n)
{
// GCD of single element is
// the element itself
for (int i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for (int j = 1; j <= log2(n); j++)
for (int i = 0; i <= n - (1 << j);
i++)
table[i][j]
= __gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
// Function to return the GCD of
// all elements in range [L, R]
int find_gcd(int L, int R)
{
// Highest power of 2 that is not
// more than count of elements
int j = (int)log2(R - L + 1);
// Return GCD in range
return __gcd(table[L][j],
table[R - (1 << j) + 1][j]);
}
// Smallest prime factors array
int spf[MAXN];
// Function to build the smallest
// prime factor array using Sieve
void build_spf()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN;
j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the count of
// distinct prime factors of x
int getFactorization(int x)
{
// Stores the required count
int ctr = 0;
while (x != 1) {
ctr++;
// Stores smallest prime
// factor of x
int p = spf[x];
while (x % p == 0)
x = x / p;
}
// Return count
return ctr;
}
// Function to count of coprime pairs such
// that the product of the pair divides
// all integers of subarray in given range
void solveQueries(vector<int> a, int n,
vector<vector<int> > q)
{
// Loop to iterate over queries
for (int i = 0; i < q.size(); i++) {
int l = q[i][0];
int r = q[i][1];
l--;
r--;
// Stores gcd in the range
int gcd = find_gcd(l, r);
// Stores the required count
int ans = 0;
// Count the pairs of co-primes
// integers in given format
for (int i = 1; i * i <= gcd; i++) {
// If i is a factor of gcd
if (gcd % i == 0) {
ans = and + (1 << getFactorization(i));
if (gcd / i != i)
ans += (1
<< getFactorization(gcd / i));
}
}
// Print answer
cout << ans << " ";
}
}
// Function to perform precomputation
void preProcess(vector<int> a, int n)
{
build_spf();
buildSparseTable(a, n);
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 2, 4, 5 };
vector<vector<int> > queries = {
{ 2, 3 }, { 2, 4 }, { 3, 4 }, { 4, 4 }, { 4, 5 }
};
preProcess(arr, arr.size());
solveQueries(arr, arr.size(), queries);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int MAXN = 200001;
static int [][]table = new int[1001][1001];
// Function to build sparse table
static void buildSparseTable(int[] arr, int n)
{
// GCD of single element is
// the element itself
for (int i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for (int j = 1; j <= Math.log(n); j++)
for (int i = 0; i <= n - (1 << j);
i++)
table[i][j]
= __gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Function to return the GCD of
// all elements in range [L, R]
static int find_gcd(int L, int R)
{
// Highest power of 2 that is not
// more than count of elements
int j = (int)Math.log(R - L + 1);
// Return GCD in range
return __gcd(table[L][j],
table[R - (1 << j) + 1][j]);
}
// Smallest prime factors array
static int []spf = new int[MAXN];
// Function to build the smallest
// prime factor array using Sieve
static void build_spf()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN;
j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the count of
// distinct prime factors of x
static int getFactorization(int x)
{
// Stores the required count
int ctr = 0;
while (x != 1) {
ctr++;
// Stores smallest prime
// factor of x
int p = spf[x];
while (x % p == 0)
x = x / p;
}
// Return count
return ctr;
}
// Function to count of coprime pairs such
// that the product of the pair divides
// all integers of subarray in given range
static void solveQueries(int [] a, int n,
int [][] q)
{
// Loop to iterate over queries
for (int i = 0; i < q.length; i++) {
int l = q[i][0];
int r = q[i][1];
l--;
r--;
// Stores gcd in the range
int gcd = find_gcd(l, r);
// Stores the required count
int ans = 0;
// Count the pairs of co-primes
// integers in given format
for (int j = 1; j * j <= gcd; j++) {
// If i is a factor of gcd
if (gcd % j == 0) {
ans = ans + (1 << getFactorization(j));
if (gcd / j != j)
ans += (1
<< getFactorization(gcd / j));
}
}
// Print answer
System.out.print(ans+ " ");
}
}
// Function to perform precomputation
static void preProcess(int [] a, int n)
{
build_spf();
buildSparseTable(a, n);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 2, 4, 5 };
int [][]queries = {
{ 2, 3 }, { 2, 4 }, { 3, 4 }, { 4, 4 }, { 4, 5 }
};
preProcess(arr, arr.length);
solveQueries(arr, arr.length, queries);
}
}
// This code is contributed by 29AjayKumar
Python3
# python program for the above approach import math MAXN = 200001 # creating 2-D table of size 1001*1001 table = [] for i in range(0, 1001): table.append([]) for j in range(0, 1001): table[i].append([]) # Function to build sparse table def buildSparseTable(arr, n): # GCD of single element is # the element itself for i in range(0, n): table[i][0] = arr[i] # Build sparse table for j in range(1, (int)(math.log2(n))+1): for i in range(0, n-(1 << j) + 1): table[i][j] = math.gcd( table[i][j - 1], table[i + (1 << (j - 1))][j - 1]) # Function to return the GCD of # all elements in range [L, R] def find_gcd(L, R): # Highest power of 2 that is not # more than count of elements j = (int)(math.log2(R - L + 1)) # Return GCD in range return math.gcd(table[L][j], table[R - (1 << j) + 1][j]) # Smallest prime factors array spf = [0]*MAXN # Function to build the smallest # prime factor array using Sieve def build_spf(): spf[1] = 1 for i in range(2, MAXN): spf[i] = i for i in range(2, MAXN, 2): spf[i] = 2 for i in range(3, (int)(math.sqrt(MAXN))): if (spf[i] == i): for j in range(i*i, MAXN, i): if (spf[j] == j): spf[j] = i # Function to find the count of # distinct prime factors of x def getFactorization(x): # Stores the required count ctr = 0 while (x != 1): ctr += 1 # Stores smallest prime # factor of x x = (int)(x) p = spf[x] while (x % p == 0): x = x // p # Return count return ctr # Function to count of coprime pairs such # that the product of the pair divides # all integers of subarray in given range def solveQueries(a, n, q): # Loop to iterate over queries for i in range(len(q)): l = q[i][0] r = q[i][1] l -= 1 r -= 1 # Stores gcd in the range gcd = find_gcd(l, r) # Stores the required count ans = 0 # Count the pairs of co-primes # integers in given format for i in range(1, (int)(math.sqrt(gcd)+1)): # If i is a factor of gcd if (gcd % i == 0): ans = ans + (1 << getFactorization(i)) if (gcd / i != i): ans += (1 << getFactorization(gcd / i)) # Print answer print(ans, end=" ") # Function to perform precomputation def preProcess(a, n): build_spf() buildSparseTable(a, n) # Driver Code arr = [1, 2, 2, 4, 5] queries = [[2, 4], [2, 4], [3, 4], [4, 4], [4, 5]] preProcess(arr, len(arr)) solveQueries(arr, len(arr), queries) # This code is contributed by rj13to.
C#
// C# program for the above approach
using System;
public class GFG{
static readonly int MAXN = 200001;
static int [,]table = new int[1001,1001];
// Function to build sparse table
static void buildSparseTable(int[] arr, int n)
{
// GCD of single element is
// the element itself
for (int i = 0; i < n; i++)
table[i,0] = arr[i];
// Build sparse table
for (int j = 1; j <= Math.Log(n); j++)
for (int i = 0; i <= n - (1 << j);
i++)
table[i,j]
= __gcd(table[i,j - 1],
table[i + (1 << (j - 1)),j - 1]);
}
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Function to return the GCD of
// all elements in range [L, R]
static int find_gcd(int L, int R)
{
// Highest power of 2 that is not
// more than count of elements
int j = (int)Math.Log(R - L + 1);
// Return GCD in range
return __gcd(table[L,j],
table[R - (1 << j) + 1,j]);
}
// Smallest prime factors array
static int []spf = new int[MAXN];
// Function to build the smallest
// prime factor array using Sieve
static void build_spf()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
spf[i] = i;
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
if (spf[i] == i) {
for (int j = i * i; j < MAXN;
j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the count of
// distinct prime factors of x
static int getFactorization(int x)
{
// Stores the required count
int ctr = 0;
while (x != 1) {
ctr++;
// Stores smallest prime
// factor of x
int p = spf[x];
while (x % p == 0)
x = x / p;
}
// Return count
return ctr;
}
// Function to count of coprime pairs such
// that the product of the pair divides
// all integers of subarray in given range
static void solveQueries(int [] a, int n,
int [,] q)
{
// Loop to iterate over queries
for (int i = 0; i < q.GetLength(0); i++) {
int l = q[i,0];
int r = q[i,1];
l--;
r--;
// Stores gcd in the range
int gcd = find_gcd(l, r);
// Stores the required count
int ans = 0;
// Count the pairs of co-primes
// integers in given format
for (int j = 1; j * j <= gcd; j++) {
// If i is a factor of gcd
if (gcd % j == 0) {
ans = ans + (1 << getFactorization(j));
if (gcd / j != j)
ans += (1
<< getFactorization(gcd / j));
}
}
// Print answer
Console.Write(ans+ " ");
}
}
// Function to perform precomputation
static void preProcess(int [] a, int n)
{
build_spf();
buildSparseTable(a, n);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 2, 2, 4, 5 };
int [,]queries = {
{ 2, 3 }, { 2, 4 }, { 3, 4 }, { 4, 4 }, { 4, 5 }
};
preProcess(arr, arr.Length);
solveQueries(arr, arr.Length, queries);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
const MAXN = 200001;
let table = new Array(1001).fill(0).map(() =>
new Array(1001).fill(0));
// Function to find gcd
const gcd = function(a, b)
{
if (!b)
{
return a;
}
return gcd(b, a % b);
}
// Function to build sparse table
const buildSparseTable = (arr, n) => {
// GCD of single element is
// the element itself
for(let i = 0; i < n; i++)
table[i][0] = arr[i];
// Build sparse table
for(let j = 1; j <= parseInt(Math.log2(n)); j++)
for(let i = 0; i <= n - (1 << j); i++)
table[i][j] = gcd(table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]);
}
// Function to return the GCD of
// all elements in range [L, R]
let find_gcd = (L, R) => {
// Highest power of 2 that is not
// more than count of elements
let j = parseInt(Math.log2(R - L + 1));
// Return GCD in range
return gcd(table[L][j], table[R - (1 << j) + 1][j]);
}
// Smallest prime factors array
let spf = new Array(MAXN).fill(0);
// Function to build the smallest
// prime factor array using Sieve
const build_spf = () => {
spf[1] = 1;
for(let i = 2; i < MAXN; i++)
spf[i] = i;
for(let i = 4; i < MAXN; i += 2)
spf[i] = 2;
for(let i = 3; i * i < MAXN; i++)
{
if (spf[i] == i)
{
for(let j = i * i; j < MAXN; j += i)
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the count of
// distinct prime factors of x
let getFactorization = (x) => {
// Stores the required count
let ctr = 0;
while (x != 1)
{
ctr++;
// Stores smallest prime
// factor of x
let p = spf[x];
while (x % p == 0)
x = parseInt(x / p);
}
// Return count
return ctr;
}
// Function to count of coprime pairs such
// that the product of the pair divides
// all integers of subarray in given range
const solveQueries = (a, n, q) => {
// Loop to iterate over queries
for(let i = 0; i < q.length; i++)
{
let l = q[i][0];
let r = q[i][1];
l--;
r--;
// Stores gcd in the range
let gcd = find_gcd(l, r);
// Stores the required count
let ans = 0;
// Count the pairs of co-primes
// integers in given format
for(let i = 1; i * i <= gcd; i++)
{
// If i is a factor of gcd
if (gcd % i == 0)
{
ans = ans + (1 << getFactorization(i));
if (parseInt(gcd / i) != i)
ans += (1 << getFactorization(
parseInt(gcd / i)));
}
}
// Print answer
document.write(`${ans} `);
}
}
// Function to perform precomputation
const preProcess = (a, n) => {
build_spf();
buildSparseTable(a, n);
}
// Driver Code
let arr = [ 1, 2, 2, 4, 5 ];
let queries = [ [ 2, 3 ], [ 2, 4 ],
[ 3, 4 ], [ 4, 4 ],
[ 4, 5 ] ];
preProcess(arr, arr.length);
solveQueries(arr, arr.length, queries);
// This code is contributed by rakeshsahni
</script>
Producción
3 3 3 5 1
Complejidad de tiempo: O(Q * sqrt(M) * log M), donde M es el número entero máximo en la array dada
Espacio auxiliar: O(M*log M)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA