Problem LinkDifficultyMediumHard PrerequisitesMath, persistent segment tree ProblemYou are given a number triangle, which is denoted as:
You are given $T$ online queries on finding the value of $LCM(L(n, 1), L(n, 2), ..., L(n, k))$ modulo $10^9+7$. How to get 30 pointsThe elements of the triangle, denoted by $L(n, k)$ are actually the denominators of the terms of Leibniz Harmonic Triangle. So, the value of $L(n, k)$ equals to $(n \cdot \binom{n1}{k1} )$. So, the answer for the query denoted by integers $n$ and $k$ will be equal to $LCM(L(n, 1), L(n, 2), ..., L(n, k)) = n \cdot LCM(\binom{n1}{0}, \binom{n1}{1}, ..., \binom{n1}{k1})$. Let's use the following equality: $(n+1) \cdot LCM(\binom{n}{0}, \binom{n}{1}, ..., \binom{n}{k})=LCM(nk+1, nk+2, ..., n+1)$. Using it, it's easy to see that the answer to the query denoted as $(n, k)$ is $LCM(nk+1, ..., n)$. So now we need to come up with a way to calculate the LCM of the consecutive numbers. For doing it, first of all, we will need a way to factorize integers fast. According to the statement, there won't be any integer greater than $10^6$, so we can use the modified sieve that not only determines whether the number prime or not, but also gives its' greater prime divisor. For doing that, any time we mark a number as a composite one, we can also remember the prime divisor that was the evidence of its' compositeness. For better understanding, have a look at the following pseudocode. Modification is highlighted in bold:
Now, when we need to get a prime factorization of an integer, we can simply divide it by its' largest prime divisor, until we get one and write out these divisors. The pseudocode that does that:
After that, primeDivisors[] will contain the factorization of an integer $n$. It isn't hard to make another list that will store each prime divisor exactly once along with its' power in the decomposition. The runtime of this factorization is $O(\log n)$. Now let's apply it to the calculation of the Least Common Multiple of the range of numbers. Consider the prime factorization of $LCM(nk+1, nk+2, ..., n)$. Obviously it will contain only prime numbers not exceeding $n$, and for each of these primes, the power in the $LCM$ will be equal to the maximal its' power in the integers between $nk+1$ and $n$. So, the solution will looks as follows:
The factorization of a single integer runs in $O(\log n)$, in a single query we will factorize no more than $M$ integers. Then, we will have to calculate the powers of no more than $M$ integers, each power can be calculated with binary exponentation in $O(\log n)$. So, the final complexity will be $O(TM \log M)$. This solution is enough for getting 30 points by solving subtasks #1 and #2, but it is too slow for solving two last subtasks. How to get 100 pointsLet's maintain the array $D_n[]$ with the following property: for each $k \leq n$ it holds that $LCM(k, k+1, ..., n) = D_n[k] \cdot D_n[k+1] \cdot ... \cdot D_n[n]$. Let's have a few examples:
Suppose that $D_{n1}$ is constructed correctly. How do we get $D_n$ using it? For the beginning, let's take $D_n = D_{n1}$ with $D_n[n] = n$. Let's note that at some $k$s, the required property won't be held. More precisely, that will be all $k$s such that there exists some $l \geq k$ such that $GCD(l, n)>1$ i.e. there is some integer $l$ greater or equal than $k$ such that it shares some prime divisors with $n$. In this case, some prime divisors will be counted twice in the $LCM$, giving the wrong result. Now, how do we get rid from these extra powers? For each prime number (say, $p$) let's store the stack of the positions of such indexes of $D_n[]$, at which the corresponding element of $D_n[]$ is currently divisible by $p$. For each position, we can also calculate the power of $p$ with which it will appear  this is basically the maximal number of times that the position number can be divided by $p$. For each prime number (say, $p$, again), its' stack will contain the positions in the decreasing order of the power of $p$ that occurs at this position, having the position with the smallest power of $p$ at the top. So in order to get rid of counting the same factor twice in the array $D_n[]$, we first decompose $n$ into a product of primes and for each prime (let $p$ be the corresponding prime number) we do the following:
The divisions can be made with the use of modular inverse, because the modulo $10^9+7$ is a prime number. It is very convenient to use persistent segment tree for calculating $D_n[]$. The segment tree should be capable of multiplying a single element and finding the product of the segment. Anytime, the won’t be more than $O(log M)$ elements in each stack, and each prime decomposition won’t contain more than $O(\log M)$ distinct prime numbers. So, it will take $O(M \log^2 M)$ to precalculate $D_1[], D_2[], …, D_M[]$. Using the property of the array $D_n[]$ you can find the $LCM$ of the consecutive range of integers with a single query to the segment tree. So it will take $O(\log M)$ to process a single query. So, the final complexity turns out to be $O(T \log M + M \log^2 M)$. Setter's SolutionCan be found here Tester's SolutionCan be found here
This question is marked "community wiki".
asked 08 Oct '15, 03:58

Well, There was another approach I used for solving this problem. We can easily reduce the above question to following : For each query of n and k, we need LCM(n−k+1,n−k+2,...,n). Now, consider an example of LCM(4,5,6,7,8). Here, if we find highest powers of all the primes which divide any of the numbers given and take product, we can get LCM. That is, for 2, we get 8; for 3, we get 3 ( 6 is divisible by 3 but no number is divisible by 9); for 5, we get 5; for 7 we get 7; for rest of the primes, we get 1. Thus, LCM(4,5,6,7,8) = 8*3*5*7 = 840. So, we build our solution on the similar basis. Say we need to find LCM(A,A+1,A+2,....,B1,B) BRIEF SOLUTION: 1. For all the primes <= sqrt(b) : we find highest power of that prime that divides a number which lies in [A,B]. 2. We find all the primes which divide a number in range [A,B] EXPLANATION: PRECALCULATIONS: 1. We can get all primes upto N in O(N) (Sieve of Eratosthenes). 2. We can also calculate PRIMEPRODUCT[N], where PRIMEPRODUCT[i] will give product of all the prime numbers <= i (mod 10^9 + 7) ( done in O(N) ) 3. We can calculate Multiplicative Modular Inverse of all PRIMEPRODUCT[n] and store in MMI[n] ( done in O(No. of Primes upto N * log(10^9 + 7)) Now for each query (A,B), we do the following steps : 1. if( A == B) return A; 2. For each prime <= sqrt(B) : Get Highest power of prime that divides a number in [A,B]. We do this via following snippet : num = primes[i]; highestpower = 1; while (num <= b) { diva = ceil(a/ num); divb = floor(b/num); if(diva<=divb){ highestpower = num; num *= primes[i]; }else{ break; } } Correctness Proof : say num * x = X; for X to lie in range [A,B], A<=X<=B => A <= num * x <= B => A/num <= x <= B/num< => There should exist an integer x, s.t. A/num <=x<=B/num. We are only concerened with integral values >= A/num and <=B/num => ceil(A/num) <=x <= floor(B/num) Thus, if diva <= divb; there exists a multiple of num in range [A,B]. 3. Now we are done with all primes <= sqrt(b). Thus, for rest of the primes, we know their hightest powers can be the numbers themselves (For query [50,100] , all the primes greater than sqrt(100) can't have a square of prime as a divisor of any number as they will exceed b. We can Calculate this by finding all primes in ranges [A/1 , B/1] , [A/2,B/2], .... [A/sqrt(b) , B/sqrt(b)] and avoiding any repitition. But this will give TLE as for this, the time complexity for each query can go upto sqrt(N). So, we use some little trick. We keep a two checks, lowcheck and highcheck. lowcheck tells that we have calculated highest powers for all primes <= lowcheck and highcheck tells that we have calculated highest powers for all primes >=highcheck. We initialize highcheck by infinity and lowcheck by sqrt(b) Now , study the following snippet : int divisor = 1; while(highcheck > lowcheck ){ high = floor(b/divisor); low = ceil(a/divisor); if (high >= highcheck) { high = highcheck1; } if (low <= lowcheck) { low = lowcheck+1; highcheck = INFINITY; } product = (PRIMEPRODUCT[high] * MMI[low1]) mod 10^9 + 7; ans = (ans * product) mod 10^9 + 7 highcheck = min(highcheck, low); divisor = max(divisor+1 , floor(b/highcheck)); } Here, low and high gives the range for which we haven't calculated the primes till now. We get product for this by getting product for all primes <= high and dividing it by product of all primes < low. Initially we take divisor =1. We update highcheck as min(highcheck, low) because for each range [A/1 , B/1] , [A/2,B/2], .... [A/sqrt(b) , B/sqrt(b)], high of former range is less than high of later range. So, we are sure that for all primes p s.t. high < p < highcheck, contribution will be of none. we calculate from low to high. thus, we have checked all the primes >= low. Now, we only need to see for high < highcheck as for others, we have already calculated. high = floor(b/divisor). Thus, divisor = max(divisor+1 , b/highcheck); (divisor + 1, to make sure it does not check for same divisor again and again). Hence, We can get the answer. COMPLEXITY: PRECALCULATIONS: O(N) + O(N) + O(1000*log(10^9 + 7)) [1000 is the number of primes <= 10^5]. FOR EACH QUERY : O(65*log(N)) [65 is number of primes upto sqrt(N)] + O(sqrt(N)). THUS, overall complexity = O(N + 1000*log(10^9 + 7) + 65*Q*log(N) + Q*sqrt(N)) answered 12 Oct '15, 19:40

I used a similar computation as @uhateme but somewhat simpler in the second part. I used a static decomposition in primes lower than sqrt(N) and higher than sqrt(N). For the "small" primes i used the same method as @uhatme. for "larger" primes I can be shure that each prime occurs in each interval queried at most once. So I precomputed a prefixproduct array (p) for an array with the value of the prime at the prime position an d 1 otherwise. The product of large primes in an interval [a,b] can then be easily computed by p[b]*p[a1]^1 mod 1000000007 answered 12 Oct '15, 23:45
Even i used kind of similar approach, for below sqrt(n) precomputed and for higer did in a loop.
(13 Oct '15, 00:22)

Can someone explain why this would be true? $(n+1)⋅LCM((^n_0),(^n_1),...,(^n_k))=LCM(n−k+1,n−k+2,...,n+1) $ answered 13 Oct '15, 18:45
To understand it better, lets move factor or (n+1) inside, so we get LCM(C(n,0)(n+1), C(n,1)(n+1), C(n,2)(n+1),...,C(n,k)(n+1)) Now expand the terms according to formula C(n,r) = [n(n1)(n2)...(nr+1)]/r!. we get => [(n+1), (n+1)n, (n+1)n(n1)/2,...] Observe that for some denom 1.2.3...d, we have terms (n+1)n*(n1)...(nd+1), i.e d+1 consecutive terms, which means that if we only consider numerator from (n+1).n.(n1)...(nd), there will be some number divisible by d, which means we don't need to disturb the new term i.e (nd+1), so these new terms (n+1),n,(n1).. contribute in LCM.
(13 Oct '15, 22:23)
they contribute in LCM on the RHS, but what about the denominators on the LHS? I don't understand your proof. And after googling a bit, I found this link: http://math.stackexchange.com/questions/1442/isthereadirectproofofthislcmidentity
(14 Oct '15, 00:46)
What i meant is all terms in denom will cancel out by numerator, for that it is sufficient to use only first d terms, no the newly added term need not take part in division, means we can use it for lcm as it differs from all previous added numbers. It can also be shown using Proof by Induction.
(14 Oct '15, 01:51)

Hi all, I have just a little a supplement.
D_i[] contains exactly i elements. stack[prime] contains all indexes of elements of D[] which are divisible by prime in decreasing order. for each n, i, D_n[i] <= i Consider array D_11[]: D = {1,1,1,1,1,1,7,4,9,10,11} // 1based stack[2 ] = {10, 8} stack[3] = {9}, stack[5] = {10}, stack[7] = {7}, stack[11] = {11} Adding 12:
answered 15 Oct '15, 22:11

Could not understand the 100 point soln . Can someone explain it properly or another way of solving thsi problem ? answered 12 Oct '15, 17:29
1
basically the idea is that for all primes <= sqrt(100000) , we can bruteforce them and for primes larger than that , their highest power will be just 1 , so we have to answer a query of the form (product of all distinct primes from l to r) where l = n  k + 1 and r = n , we this we can use a persistent segment tree , for more details about queries regarding distinct numbers , refer to august long challenge > simple queries editorial . here is my implementation https://www.codechef.com/viewsolution/8442793
(12 Oct '15, 21:34)

This is the way I used for factorizing integers from 1 to m. This does the job with almost no extra cost in terms of time than the Sieve of Eratosthenes. It exploits the fact that the largest exponent of a prime P in an integer N is equal to ( 1 + largest exponent of the prime in N/P ).
answered 13 Oct '15, 01:04

How many elements does each answered 14 Oct '15, 15:54

How can someone come up with the fact that the F(N,K) of the problem was related to Leibniz Harmonic Triangle? answered 15 Oct '15, 08:14

I think the correct time complexity for the author's solution is $\mathcal{O}\left(N \log N \log M \sum_{p}\frac{1}{p\log p}\right)$ where $p$ are primes are less than $M$. But since $\sum_{p}\frac{1}{p\log p} \approx 1.55$ for $M = 10^5$, we can say that the complexity is equivalent to $\mathcal{O}(N\log N \log M)$ answered 10 Apr '17, 17:22
