Prime Factorization, Binary Search, Segment Tree/ Merge Sort Tree
Given N numbers and Q queries, for each query find sum of number of prime numbers which are between X to Y (both inclusive) in prime factorization of numbers from L to R (both inclusive).
As this is not official editorial i directly jump to full solution. for subtask 1 brute force should pass, for second subtask my sqrt solution gets 30 points linked below.
The idea is to use Segment Tree pretty much like standard one but with few modifications. Like in normal Segment Tree for sum queries, in each node we store sum of numbers for range represented by the node, here we store prime numbers in prime factorization of numbers represented by range of that node and also maintain count of prime numbers.
For fast queries using binary search we store it in sorted order and calculate prefix sum for each node later.
Building the Segment tree:
Let’s start with leaf nodes which represent one number, as stated above we store primes in it’s factorization and their count in sorted order let say we store in an array then it’s maximum size can be 8 as 21 * 3 1 * 51 * 71 * 111 * 131 * 171 * 191 > Max(a[i]).
Now we build inner nodes, they just contain primes in list of their sons. which is like merging list of sons into one. let’s find length of list contained in these nodes let it represents range of length L also for worst case let no prime factor is common among those elements so max length can be 8 * L as each may have at most 8 prime factors.
check build function for details
complexity analysis: O(NlgN)
merging 2 lists of length O(L/2) takes O(L) time.
at level 1, 1 node of length N => take O(N) time.
at level 2, 2 nodes of length N/2 => 2 * O(N/2) = N
at last level N node of length 1 => N * O(1) = N
summing at each level gives total O(NlgN) time complexity for building.
Memory complexity: O(NlgN)
Let say we have query L, R, X, Y as given in problem. It’s same as normal one except one modification, from each node that is queried we want sum of count of primes between Y to X, binary search is used here.
check query function.
(https://www.codechef.com/viewsolution/14145975) for subtask 1 and 2. Segment Tree/Merge Sort Tree like
(https://www.codechef.com/viewsolution/14243341) full solution.
this is my first blog post feel free to ask in comments