Moving From Mediocrity

Hello folks. Hope you are having a good time. I wanted to share my solution to CodeChef June '17 problem   PRMQ . Though there might be many solutions possible to this problem, I will walk you through a Segment-Tree solution for this. Approach There are nearly 78,000 prime numbers between 1 and 10^6, so in worst case a number in this query range L to R can have maximum of 8 prime numbers as the number of factors. Why 8 see 2*3*5*7*11*13*17*19 > 10^6 . And the root node can have maximum of 78,000 nodes with each prime number in the leaf node merging to form the root node. Now let us think what we should store in a node of segment tree. We may need the following information:- 1. The element of the array so as to compute their prime factors. 2. Some way to combine the factors of each element as key and their count as value, suppose we are having 2 elements say 8 and 9 so when we merge these node in the tree, we have got 2 as a factor with count 3 and 3 as a factor with

Just wanted to introduce you to very basic concept of Modular Exponentiation through a problem,  Big Mod . We need to calculate A^B % M for large inputs. For a second let's forget about A^B  % M and think about A^B only and say A^B lies within the range of long long int and B is less than 10^7. A basic brute force approach to calculate A^B will be to loop through 1 to B and multiply A every time. The time complexity of this approach is O(n). This is perfect on current constraints but what happens if I change the constraint on B and raise it to 10^12 or so. Now  this approach will give a TLE. An efficient approach is needed. O(n) is not sufficient. We will use a recursive approach for this. Suppose I want to calculate A^B but if B is even, I can calculate A^(B/2) and multiply it to itself, and the way to calculate A^(B/2) is to calculate A^(B/4) and so on you get the idea. But what if B is not even, no problem,  B-1 will be even do the same except replace B with B-1 and separ