Given an array arr of size N and Q queries of the form [L, R], the task is to find the number of divisors of the product of this array in the given range.
Note: The ranges are 1-positioned.
Constraints: 1<= N, Q <= 105, 1<= arr[i] <= 106.
Examples:
Input: arr[] = {4, 1, 9, 12, 5, 3}, Q = {{1, 3}, {3, 5}}
Output: 9
24Input: arr[] = {5, 2, 3, 1, 4}, Q = {{2, 4}, {1, 5}}
Output: 4
16
Brute force:
- For every Query, iterate array from L to R and calculate the product of elements in the given range.
- Calculate the total number of divisors of that product.
Time Complexity: Q * N * (log (N))
Efficient Approach: The idea is to use Segment Tree to solve this problem.
- We can’t store the product of array from L to R because of the constraints so we can store the power of prime in segment tree.
- For every query, we merge the trees according to the query.
Construction of Segment Tree from given array
- We start with a segment arr[0 . . . n-1].
- Every time we divide the current segment into two halves, if it has not yet become a segment of length 1.
- Then call the same procedure on both halves, and for each such segment, we store the power of primes in the corresponding node.
- All levels of the constructed segment tree will be completely filled except the last level.
- Also, the tree will be a Full Binary Tree because we always divide segments into two halves at every level.
- Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;#define ll long long int#define MOD 1000000007#define MAXN 1000001// Array to store the precomputed prime numbersint spf[MAXN];// Function signaturesvoid merge( vector<pair<int, int> > tree[], int treeIndex);void sieve();vector<int> getFactorization( int x);void buildTree( vector<pair<int, int> > tree[], int treeIndex, int start, int end, int arr[]);int query( vector<pair<int, int> > tree[], int treeIndex, int start, int end, int left, int right);vector<pair<int, int> > mergeUtil( vector<pair<int, int> > op1, vector<pair<int, int> > op2);vector<pair<int, int> > queryUtil( vector<pair<int, int> > tree[], int treeIndex, int start, int end, int left, int right);// Function to use Sieve to compute// and store prime numbersvoid sieve(){ 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// prime factors of a valuevector<int> getFactorization(int x){ // Vector to store the prime factors vector<int> ret; // For every prime factor of x, // push it to the vector while (x != 1) { ret.push_back(spf[x]); x = x / spf[x]; } // Return the prime factors return ret;}// Recursive function to build segment tree// by merging the power of primesvoid buildTree(vector<pair<int, int> > tree[], int treeIndex, int start, int end, int arr[]){ // Base case if (start == end) { int val = arr[start]; vector<int> primeFac = getFactorization(val); for (auto it : primeFac) { int power = 0; while (val % it == 0) { val = val / it; power++; } // Storing powers of prime // in tree at treeIndex tree[treeIndex] .push_back({ it, power }); } return; } int mid = (start + end) / 2; // Building the left tree buildTree(tree, 2 * treeIndex, start, mid, arr); // Building the right tree buildTree(tree, 2 * treeIndex + 1, mid + 1, end, arr); // Merges the right tree and left tree merge(tree, treeIndex); return;}// Function to merge the right// and the left treevoid merge(vector<pair<int, int> > tree[], int treeIndex){ int index1 = 0; int index2 = 0; int len1 = tree[2 * treeIndex].size(); int len2 = tree[2 * treeIndex + 1].size(); // Fill this array in such a way such that values // of prime remain sorted similar to mergesort while (index1 < len1 && index2 < len2) { // If both of the elements are same if (tree[2 * treeIndex][index1].first == tree[2 * treeIndex + 1][index2].first) { tree[treeIndex].push_back( { tree[2 * treeIndex][index1].first, tree[2 * treeIndex][index1].second + tree[2 * treeIndex + 1] [index2] .second }); index1++; index2++; } // If the element on the left part // is greater than the right part else if (tree[2 * treeIndex][index1].first > tree[2 * treeIndex + 1][index2].first) { tree[treeIndex].push_back( { tree[2 * treeIndex + 1][index2].first, tree[2 * treeIndex + 1][index2].second }); index2++; } // If the element on the left part // is less than the right part else { tree[treeIndex].push_back( { tree[2 * treeIndex][index1].first, tree[2 * treeIndex][index1].second }); index1++; } } // Insert the leftover elements // from the left part while (index1 < len1) { tree[treeIndex].push_back( { tree[2 * treeIndex][index1].first, tree[2 * treeIndex][index1].second }); index1++; } // Insert the leftover elements // from the right part while (index2 < len2) { tree[treeIndex].push_back( { tree[2 * treeIndex + 1][index2].first, tree[2 * treeIndex + 1][index2].second }); index2++; } return;}// Function similar to merge() method// But here it takes two vectors and// return a vector of power of primesvector<pair<int, int> > mergeUtil( vector<pair<int, int> > op1, vector<pair<int, int> > op2){ int index1 = 0; int index2 = 0; int len1 = op1.size(); int len2 = op2.size(); vector<pair<int, int> > res; while (index1 < len1 && index2 < len2) { if (op1[index1].first == op2[index2].first) { res.push_back({ op1[index1].first, op1[index1].second + op2[index2].second }); index1++; index2++; } else if (op1[index1].first > op2[index2].first) { res.push_back({ op2[index2].first, op2[index2].second }); index2++; } else { res.push_back({ op1[index1].first, op1[index1].second }); index1++; } } while (index1 < len1) { res.push_back({ op1[index1].first, op1[index1].second }); index1++; } while (index2 < len2) { res.push_back({ op2[index2].first, op2[index2].second }); index2++; } return res;}// Function similar to query() method// as in segment tree// Here also the result is mergedvector<pair<int, int> > queryUtil( vector<pair<int, int> > tree[], int treeIndex, int start, int end, int left, int right){ if (start > right || end < left) { tree[0].clear(); return tree[0]; } if (start >= left && end <= right) { return tree[treeIndex]; } int mid = (start + end) / 2; vector<pair<int, int> > op1 = queryUtil(tree, 2 * treeIndex, start, mid, left, right); vector<pair<int, int> > op2 = queryUtil(tree, 2 * treeIndex + 1, mid + 1, end, left, right); return mergeUtil(op1, op2);}// Function to return the number of divisors// of product of array from left to rightint query(vector<pair<int, int> > tree[], int treeIndex, int start, int end, int left, int right){ vector<pair<int, int> > res = queryUtil(tree, treeIndex, start, end, left, right); int sum = 1; for (auto it : res) { sum *= (it.second + 1); sum %= MOD; } return sum;}// Function to solve queriesvoid solveQueries( int arr[], int len, int l, int r){ // Calculate the size of segment tree int x = (int)(ceil(log2(len))); // Maximum size of segment tree int max_size = 2 * (int)pow(2, x) - 1; // first of pair is used to store the prime // second of pair is use to store its power vector<pair<int, int> > tree[max_size]; // building the tree buildTree(tree, 1, 0, len - 1, arr); // Find the required number of divisors // of product of array from l to r cout << query(tree, 1, 0, len - 1, l - 1, r - 1) << endl;}// Driver codeint main(){ // Precomputing the prime numbers using sieve sieve(); int arr[] = { 5, 2, 3, 1, 4 }; int len = sizeof(arr) / sizeof(arr[0]); int queries = 2; int Q[queries][2] = { { 2, 4 }, { 1, 5 } }; // Solve the queries for (int i = 0; i < queries; i++) { solveQueries(arr, len, Q[i][0], Q[i][1]); } return 0;} |
Java
import java.util.ArrayList;public class Main { static final int MOD = 1000000007; static final int MAXN = 1000001; // Array to store the precomputed prime numbers static int[] spf = new int[MAXN]; // Function to use Sieve to compute // and store prime numbers static void sieve() { 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 prime factors of a value static ArrayList<Integer> getFactorization(int x) { ArrayList<Integer> ret = new ArrayList<>(); while (x != 1) { ret.add(spf[x]); x /= spf[x]; } return ret; } // Function to merge the right and left tree static void merge(ArrayList<int[]>[] tree, int treeIndex) { int index1 = 0; int index2 = 0; int len1 = tree[2 * treeIndex].size(); int len2 = tree[2 * treeIndex + 1].size(); ArrayList<int[]> mergedAns = new ArrayList<>(); while (index1 < len1 && index2 < len2) { if (tree[2 * treeIndex].get(index1)[0] == tree[2 * treeIndex + 1].get(index2)[0]) { int[] temp = { tree[2 * treeIndex].get(index1)[0], (tree[2 * treeIndex].get(index1)[1] + tree[2 * treeIndex + 1].get( index2)[1]) % MOD }; mergedAns.add(temp); index1++; index2++; } else if (tree[2 * treeIndex].get(index1)[0] < tree[2 * treeIndex + 1].get( index2)[0]) { mergedAns.add( tree[2 * treeIndex].get(index1)); index1++; } else { mergedAns.add( tree[2 * treeIndex + 1].get(index2)); index2++; } } while (index1 < len1) { mergedAns.add(tree[2 * treeIndex].get(index1)); index1++; } while (index2 < len2) { mergedAns.add( tree[2 * treeIndex + 1].get(index2)); index2++; } tree[treeIndex] = mergedAns; } // Recursive function to build a segment tree static void buildTree(ArrayList<int[]>[] tree, int treeIndex, int start, int end, int[] arr) { if (start == end) { int val = arr[start]; ArrayList<Integer> primeFac = getFactorization(val); for (int it : primeFac) { int power = 0; while (val % it == 0) { val = val / it; power++; } int[] temp = { it, power }; tree[treeIndex].add(temp); } return; } int mid = (start + end) / 2; buildTree(tree, 2 * treeIndex, start, mid, arr); buildTree(tree, 2 * treeIndex + 1, mid + 1, end, arr); merge(tree, treeIndex); } // Function to return the number of divisors // of a product of an array from left to right static int query(ArrayList<int[]>[] tree, int treeIndex, int start, int end, int left, int right) { ArrayList<int[]> res = queryUtil( tree, treeIndex, start, end, left, right); int sum = 1; for (int[] it : res) { sum *= (it[1] + 1); sum %= MOD; } return sum; } // Function similar to merge() method // But here it takes two vectors and // returns a vector of the power of primes static ArrayList<int[]> mergeUtil(ArrayList<int[]> op1, ArrayList<int[]> op2) { int index1 = 0; int index2 = 0; int len1 = op1.size(); int len2 = op2.size(); ArrayList<int[]> mergedAns = new ArrayList<>(); while (index1 < len1 && index2 < len2) { if (op1.get(index1)[0] == op2.get(index2)[0]) { int[] temp = { op1.get(index1)[0], (op1.get(index1)[1] + op2.get(index2)[1]) % MOD }; mergedAns.add(temp); index1++; index2++; } else if (op1.get(index1)[0] < op2.get(index2)[0]) { mergedAns.add(op1.get(index1)); index1++; } else { mergedAns.add(op2.get(index2)); index2++; } } while (index1 < len1) { mergedAns.add(op1.get(index1)); index1++; } while (index2 < len2) { mergedAns.add(op2.get(index2)); index2++; } return mergedAns; } // Function to merge the right // and the left tree static ArrayList<int[]> queryUtil(ArrayList<int[]>[] tree, int treeIndex, int start, int end, int left, int right) { if (left > end || right < start) { return new ArrayList<>(); } if (left <= start && end <= right) { return tree[treeIndex]; } int mid = (start + end) / 2; ArrayList<int[]> op1 = queryUtil( tree, 2 * treeIndex, start, mid, left, right); ArrayList<int[]> op2 = queryUtil(tree, 2 * treeIndex + 1, mid + 1, end, left, right); return mergeUtil(op1, op2); } // Function to solve queries static void solveQueries(int[] arr, int len, int l, int r) { int x = (int)Math.ceil(Math.log(len) / Math.log(2)); int max_size = 2 * (int)Math.pow(2, x) - 1; ArrayList<int[]>[] tree = new ArrayList[max_size]; for (int i = 0; i < tree.length; i++) { tree[i] = new ArrayList<>(); } buildTree(tree, 1, 0, len - 1, arr); System.out.println( query(tree, 1, 0, len - 1, l - 1, r - 1)); } public static void main(String[] args) { // Precomputing the prime numbers using sieve sieve(); int[] arr = { 5, 2, 3, 1, 4 }; int len = arr.length; int queries = 2; int[][] Q = { { 2, 4 }, { 1, 5 } }; // Solve the queries for (int i = 0; i < queries; i++) { solveQueries(arr, len, Q[i][0], Q[i][1]); } }} |
Python3
from typing import List, Tuplefrom math import ceil, log2, powimport syssys.setrecursionlimit(10000)MOD = 1000000007MAXN = 1000001# Array to store the precomputed prime numbersspf = [0 for _ in range(MAXN)]# Function to use Sieve to compute# and store prime numbersdef sieve() -> None: spf[1] = 1 for i in range(2, MAXN): spf[i] = i for i in range(4, MAXN, 2): spf[i] = 2 i = 3 while i * i < MAXN: if (spf[i] == i): for j in range(i * i, MAXN, i): if (spf[j] == j): spf[j] = i i += 1# Function to find the# prime factors of a valuedef getFactorization(x: int) -> List[int]: # Vector to store the prime factors ret = [] # For every prime factor of x, # push it to the vector while (x != 1): ret.append(spf[x]) x = x // spf[x] # Return the prime factors return ret# Recursive function to build segment tree# by merging the power pf primesdef buildTree(tree: List[List[Tuple[int]]], treeIndex: int, start: int, end: int, arr: List[int]) -> None: # Base case if (start == end): val = arr[start] primeFac = getFactorization(val) for it in primeFac: power = 0 while (val % it == 0): val = val // it power += 1 # Storing powers of prime # in tree at treeIndex tree[treeIndex].append((it, power)) return mid = (start + end) // 2 # Building the left tree buildTree(tree, 2 * treeIndex, start, mid, arr) # Building the right tree buildTree(tree, 2 * treeIndex + 1, mid + 1, end, arr) # Merges the right tree and left tree merge(tree, treeIndex) return# Function to merge the right# and the left treedef merge(tree: List[List[Tuple[int]]], treeIndex: int) -> None: index1 = 0 index2 = 0 len1 = len(tree[2 * treeIndex]) len2 = len(tree[2 * treeIndex + 1]) # Fill this array in such a way such that values # of prime remain sorted similar to mergesort while (index1 < len1 and index2 < len2): # If both of the elements are same if (tree[2 * treeIndex][index1][0] == tree[2 * treeIndex + 1][index2][0]): tree[treeIndex].append((tree[2 * treeIndex][index1][0], tree[2 * treeIndex][index1][1] + tree[2 * treeIndex + 1][index2][1])) index1 += 1 index2 += 1 # If the element on the left part # is greater than the right part elif (tree[2 * treeIndex][index1][0] > tree[2 * treeIndex + 1][index2][0]): tree[treeIndex].append((tree[2 * treeIndex + 1][index2][0], tree[2 * treeIndex + 1][index2][1])) index2 += 1 # If the element on the left part # is less than the right part else: tree[treeIndex].append((tree[2 * treeIndex][index1][0], tree[2 * treeIndex][index1][1])) index1 += 1 # Insert the leftover elements # from the left part while (index1 < len1): tree[treeIndex].append( (tree[2 * treeIndex][index1][0], tree[2 * treeIndex][index1][1])) index1 += 1 # Insert the leftover elements # from the right part while (index2 < len2): tree[treeIndex].append((tree[2 * treeIndex + 1][index2][0], tree[2 * treeIndex + 1][index2][1])) index2 += 1 return# Function similar to merge() method# But here it takes two vectors and# return a vector of power of primesdef mergeUtil(op1: List[Tuple[int]], op2: List[Tuple[int]]) -> List[Tuple[int]]: index1 = 0 index2 = 0 len1 = len(op1) len2 = len(op2) res = [] while (index1 < len1 and index2 < len2): if (op1[index1][0] == op2[index2][0]): res.append((op1[index1][0], (op1[index1][1] + op2[index2][1]))) index1 += 1 index2 += 1 elif (op1[index1][0] > op2[index2][0]): res.append((op2[index2][0], op2[index2][1])) index2 += 1 else: res.append((op1[index1][0], op1[index1][1])) index1 += 1 while (index1 < len1): res.append((op1[index1][0], op1[index1][1])) index1 += 1 while (index2 < len2): res.append((op2[index2][0], op2[index2][1])) index2 += 1 return res# Function similar to query() method# as in segment tree# Here also the result is mergeddef queryUtil(tree: List[List[Tuple[int]]], treeIndex: int, start: int,end: int, left: int, right: int) -> List[Tuple[int]]: if (start > right or end < left): tree[0].clear() return tree[0] if (start >= left and end <= right): return tree[treeIndex] mid = (start + end) // 2 op1 = queryUtil(tree, 2 * treeIndex, start, mid, left, right) op2 = queryUtil(tree, 2 * treeIndex + 1, mid + 1, end, left, right) return mergeUtil(op1, op2)# Function to return the number of divisors# of product of array from left to rightdef query(tree: List[List[Tuple[int]]], treeIndex: int, start: int, end: int, left: int, right: int) -> int: res = queryUtil(tree, treeIndex, start, end, left, right) sum = 1 for it in res: sum *= (it[1] + 1) sum %= MOD return sum# Function to solve queriesdef solveQueries(arr: List[int], length: int, l: int, r: int) -> None: # Calculate the size of segment tree x = int(ceil(log2(length))) # Maximum size of segment tree max_size = 2 * int(pow(2, x)) - 1 # First of pair is used to store the prime # second of pair is use to store its power tree = [[] for _ in range(max_size)] # building the tree buildTree(tree, 1, 0, length - 1, arr) # Find the required number of divisors # of product of array from l to r print(query(tree, 1, 0, length - 1, l - 1, r - 1))# Driver codeif __name__ == "__main__": # Precomputing the prime numbers using sieve sieve() arr = [ 5, 2, 3, 1, 4 ] length = len(arr) queries = 2 Q = [ [ 2, 4 ], [ 1, 5 ] ] # Solve the queries for i in range(queries): solveQueries(arr, length, Q[i][0], Q[i][1])# This code is contributed by sanjeev2552 |
C#
using System;using System.Collections.Generic;class GFG { // Constants for maximum array size and MOD value const int MAXN = 1000001; const int MOD = 1000000007; // Array to store the precomputed prime numbers static int[] spf = new int[MAXN]; // Function to use Sieve to compute // and store prime numbers static void Sieve() { 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 prime factors of a value static List<int> GetFactorization(int x) { List<int> ret = new List<int>(); while (x != 1) { ret.Add(spf[x]); x = x / spf[x]; } return ret; } // Recursive function to build segment tree by merging // the power of primes static void BuildTree(List<Tuple<int, int> >[] tree, int treeIndex, int start, int end, int[] arr) { if (start == end) { int val = arr[start]; List<int> primeFac = GetFactorization(val); foreach(int it in primeFac) { int power = 0; while (val % it == 0) { val = val / it; power++; } tree[treeIndex].Add( Tuple.Create(it, power)); } return; } int mid = (start + end) / 2; BuildTree(tree, 2 * treeIndex, start, mid, arr); BuildTree(tree, 2 * treeIndex + 1, mid + 1, end, arr); Merge(tree, treeIndex); } // Function to merge the right and the left tree static void Merge(List<Tuple<int, int> >[] tree, int treeIndex) { int index1 = 0; int index2 = 0; int len1 = tree[2 * treeIndex].Count; int len2 = tree[2 * treeIndex + 1].Count; List<Tuple<int, int> > merged = new List<Tuple<int, int> >(); while (index1 < len1 && index2 < len2) { if (tree[2 * treeIndex][index1].Item1 == tree[2 * treeIndex + 1][index2].Item1) { merged.Add(Tuple.Create( tree[2 * treeIndex][index1].Item1, tree[2 * treeIndex][index1].Item2 + tree[2 * treeIndex + 1][index2] .Item2)); index1++; index2++; } else if (tree[2 * treeIndex][index1].Item1 > tree[2 * treeIndex + 1][index2] .Item1) { merged.Add(Tuple.Create( tree[2 * treeIndex + 1][index2].Item1, tree[2 * treeIndex + 1][index2].Item2)); index2++; } else { merged.Add(Tuple.Create( tree[2 * treeIndex][index1].Item1, tree[2 * treeIndex][index1].Item2)); index1++; } } while (index1 < len1) { merged.Add(Tuple.Create( tree[2 * treeIndex][index1].Item1, tree[2 * treeIndex][index1].Item2)); index1++; } while (index2 < len2) { merged.Add(Tuple.Create( tree[2 * treeIndex + 1][index2].Item1, tree[2 * treeIndex + 1][index2].Item2)); index2++; } tree[treeIndex] = merged; } // Function to return the number of divisors of product // of array from left to right static int Query(List<Tuple<int, int> >[] tree, int treeIndex, int start, int end, int left, int right) { List<Tuple<int, int> > result = QueryUtil( tree, treeIndex, start, end, left, right); int sum = 1; foreach(Tuple<int, int> it in result) { sum *= (it.Item2 + 1); sum %= MOD; } return sum; } // Function similar to query() method as in the segment // tree static List<Tuple<int, int> > QueryUtil(List<Tuple<int, int> >[] tree, int treeIndex, int start, int end, int left, int right) { if (start > right || end < left) { tree[0].Clear(); return tree[0]; } if (start >= left && end <= right) { return tree[treeIndex]; } int mid = (start + end) / 2; List<Tuple<int, int> > op1 = QueryUtil( tree, 2 * treeIndex, start, mid, left, right); List<Tuple<int, int> > op2 = QueryUtil(tree, 2 * treeIndex + 1, mid + 1, end, left, right); return MergeUtil(op1, op2); } // Function similar to merge() method but here it takes // two lists and returns a list of power of primes static List<Tuple<int, int> > MergeUtil(List<Tuple<int, int> > op1, List<Tuple<int, int> > op2) { int index1 = 0; int index2 = 0; int len1 = op1.Count; int len2 = op2.Count; List<Tuple<int, int> > res = new List<Tuple<int, int> >(); while (index1 < len1 && index2 < len2) { if (op1[index1].Item1 == op2[index2].Item1) { res.Add(Tuple.Create( op1[index1].Item1, op1[index1].Item2 + op2[index2].Item2)); index1++; index2++; } else if (op1[index1].Item1 > op2[index2].Item1) { res.Add(Tuple.Create(op2[index2].Item1, op2[index2].Item2)); index2++; } else { res.Add(Tuple.Create(op1[index1].Item1, op1[index1].Item2)); index1++; } } while (index1 < len1) { res.Add(Tuple.Create(op1[index1].Item1, op1[index1].Item2)); index1++; } while (index2 < len2) { res.Add(Tuple.Create(op2[index2].Item1, op2[index2].Item2)); index2++; } return res; } // Function to solve queries static void SolveQueries(int[] arr, int len, int left, int right) { int x = (int)Math.Ceiling(Math.Log(len, 2)); int max_size = 2 * (int)Math.Pow(2, x) - 1; List<Tuple<int, int> >[] tree = new List<Tuple<int, int> >[ max_size ]; for (int i = 0; i < max_size; i++) { tree[i] = new List<Tuple<int, int> >(); } BuildTree(tree, 1, 0, len - 1, arr); Console.WriteLine(Query(tree, 1, 0, len - 1, left - 1, right - 1)); } // Driver code static void Main() { // Precomputing the prime numbers using sieve Sieve(); int[] arr = { 5, 2, 3, 1, 4 }; int len = arr.Length; int queries = 2; int[, ] Q = { { 2, 4 }, { 1, 5 } }; for (int i = 0; i < queries; i++) { SolveQueries(arr, len, Q[i, 0], Q[i, 1]); } }} |
Javascript
<script> //JavaScript code for the above approach const MOD = 1000000007; const MAXN = 1000001; let spf = new Array(MAXN); function merge(tree, treeIndex) { let index1 = 0; let index2 = 0; let len1 = tree[2 * treeIndex].length; let len2 = tree[2 * treeIndex + 1].length; while (index1 < len1 && index2 < len2) { if (tree[2 * treeIndex][index1][0] === tree[2 * treeIndex + 1][index2][0]) { tree[treeIndex].push([tree[2 * treeIndex][index1][0], (tree[2 * treeIndex][index1][1] + tree[2 * treeIndex + 1][index2][1]) % MOD, ]); index1++; index2++; } else if (tree[2 * treeIndex][index1][0] < tree[2 * treeIndex + 1][index2][0]) { tree[treeIndex].push(tree[2 * treeIndex][index1]); index1++; } else { tree[treeIndex].push(tree[2 * treeIndex + 1][index2]); index2++; } } while (index1 < len1) { tree[treeIndex].push(tree[2 * treeIndex][index1]); index1++; } while (index2 < len2) { tree[treeIndex].push(tree[2 * treeIndex + 1][index2]); index2++; } } function sieve() { 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 getFactorization(x) { let ret = []; while (x !== 1) { ret.push(spf[x]); x = Math.floor(x / spf[x]); } return ret; } function buildTree(tree, treeIndex, start, end, arr) { if (start === end) { let val = arr[start]; let primeFac = getFactorization(val); for (let it of primeFac) { let power = 0; while (val % it === 0) { val = Math.floor(val / it); power++; } tree[treeIndex].push([it, power]); } return; } let mid = Math.floor((start + end) / 2); buildTree(tree, 2 * treeIndex, start, mid, arr); buildTree(tree, 2 * treeIndex + 1, mid + 1, end, arr); merge(tree, treeIndex); return; } function query(tree, treeIndex, start, end, left, right) { if (left > end || right < start) { return []; } if (left <= start && end <= right) { return tree[treeIndex]; } let mid = Math.floor((start + end) / 2); let op1 = query(tree, 2 * treeIndex, start, mid, left, right); let op2 = query(tree, 2 * treeIndex + 1, mid + 1, end, left, right); return mergeUtil(op1, op2); } function mergeUtil(op1, op2) { let index1 = 0; let index2 = 0; let len1 = op1.length; let len2 = op2.length; let mergedAns = []; while (index1 < len1 && index2 < len2) { if (op1[index1][0] === op2[index2][0]) { mergedAns.push([ op1[index1][0], (op1[index1][1] + op2[index2][1]) % MOD, ]); index1++; index2++; } else if (op1[index1][0] < op2[index2][0]) { mergedAns.push(op1[index1]); index1++; } else { mergedAns.push(op2[index2]); index2++; } } while (index1 < len1) { mergedAns.push(op1[index1]); index1++; } while (index2 < len2) { mergedAns.push(op2[index2]); index2++; } return mergedAns; } function queryUtil(tree, treeIndex, start, end, left, right) { if (left > end || right < start) { return []; } if (left <= start && end <= right) { return tree[treeIndex]; } let mid = Math.floor((start + end) / 2); let op1 = queryUtil(tree, 2 * treeIndex, start, mid, left, right); let op2 = queryUtil(tree, 2 * treeIndex + 1, mid + 1, end, left, right); return mergeUtil(op1, op2); } function query(tree, treeIndex, start, end, left, right) { let res = queryUtil(tree, treeIndex, start, end, left, right); let sum = 1; for (let it of res) { sum *= (it[1] + 1); sum %= MOD; } return sum; } function solveQueries(arr, len, l, r) { let x = Math.ceil(Math.log2(len)); let max_size = 2 * Math.pow(2, x) - 1; let tree = new Array(max_size); for (let i = 0; i < tree.length; i++) { tree[i] = []; } buildTree(tree, 1, 0, len - 1, arr); document.write(query(tree, 1, 0, len - 1, l - 1, r - 1)+"<br>"); } sieve(); let arr = [5, 2, 3, 1, 4]; let len = arr.length; let queries = 2; let Q = [[2, 4], [1, 5], ]; for (let i = 0; i < queries; i++) { solveQueries(arr, len, Q[i][0], Q[i][1]); } // This code is contributed by Potta Lokesh</script> |
Output
4 16
Time Complexity: Q * (log (N))
Space complexity: O(MAXN+N*log(N))
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!
