Given an array arr[] of N integers and Q queries of the form (l, r). The task is to find the number of distinct pairs of coprime integers for each query such that all integers in index range [l, r] are divisible by the product of the coprime integers.
Examples:
Input: arr[] = {1, 2, 2, 4, 5}, queries[] = {{2, 3}, {2, 4}, {3, 4}, {4, 4}, {4, 5}}
Output: 3 3 3 5 1
Explanation: For 1st query [2, 3], the subarray is {2, 2}.
The pairs of coprimes that divide all the integers in the subarray are {1, 1}, {1, 2} and {2, 1}.
For 2nd query [2, 4], the subarray is {2, 2, 4}.
The pairs of coprimes that divide all the integers are {1, 1}, {1, 2} and {2, 1}.
Similarly, proceed for the further queries.Input: arr[] = {20, 10, 15}, queries[] = {{2, 3}, {1, 3}, {1, 2}}
Output: 3 3 9
Approach: The given problem can be optimally solved with the help of a sparse table. The approach is based on the fact that only the prime factors of the GCD of a subarray can divide all its elements. Hence, the prime factors of GCD contribute to the count of pairs. The GCD of the ranges can be calculated optimally using a sparse table. Below are the steps to follow:
- Create a sparse table to find the GCD elements in the range [L, R] in optimal time over multiple queries.
- Iterate through the query array and for each query, perform the following:
- Find the GCD of elements in the range [L, R] for the current query.
- The problem is now reduced to finding the number of coprime pairs in the range [1, GCD] having their product as GCD which can be done using the algorithm discussed here.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAXN 200001int table[1001][1001];// Function to build sparse tablevoid 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 arrayint spf[MAXN];// Function to build the smallest// prime factor array using Sievevoid 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 xint 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 rangevoid 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 precomputationvoid preProcess(vector<int> a, int n){ build_spf(); buildSparseTable(a, n);}// Driver Codeint 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 approachimport 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 approachimport mathMAXN = 200001# creating 2-D table of size 1001*1001table = []for i in range(0, 1001): table.append([]) for j in range(0, 1001): table[i].append([])# Function to build sparse tabledef 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 arrayspf = [0]*MAXN# Function to build the smallest# prime factor array using Sievedef 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 xdef 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 rangedef 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 precomputationdef preProcess(a, n): build_spf() buildSparseTable(a, n)# Driver Codearr = [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 approachusing 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 approachconst MAXN = 200001;let table = new Array(1001).fill(0).map(() => new Array(1001).fill(0));// Function to find gcdconst gcd = function(a, b){ if (!b) { return a; } return gcd(b, a % b);}// Function to build sparse tableconst 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 arraylet spf = new Array(MAXN).fill(0);// Function to build the smallest// prime factor array using Sieveconst 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 xlet 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 rangeconst 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 precomputationconst preProcess = (a, n) => { build_spf(); buildSparseTable(a, n);}// Driver Codelet 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> |
Output
3 3 3 5 1
Time Complexity: O(Q * sqrt(M) * log M), where M is the maximum integer in the given array
Auxiliary Space: O(M*log M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
