# Problem Link

# Difficulty

Medium-Hard

# Pre-requisites

Math, persistent segment tree

# Problem

You are given a number triangle, which is denoted as:

- L(n, 1) = n
- L(n, k) = (\frac{1}{L(n - 1, k - 1)}-\frac{1}{L(n, k-1)})^{-1}

You are given T on-line queries on finding the value of LCM(L(n, 1), L(n, 2), ..., L(n, k)) modulo 10^9+7.

# How to get 30 points

The 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{n-1}{k-1} ). 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{n-1}{0}, \binom{n-1}{1}, ..., \binom{n-1}{k-1}).

Let’s use the following equality: (n+1) \cdot LCM(\binom{n}{0}, \binom{n}{1}, ..., \binom{n}{k})=LCM(n-k+1, n-k+2, ..., n+1). Using it, it’s easy to see that the answer to the query denoted as (n, k) is LCM(n-k+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:

` for i = 2 to n :`

isPrime* = true, largestPrimeDivisor* = 0

for i = 2 to n :

if isPrime* :

**largestPrimeDivisor* = i**

j = i + i

while j <= n :

isPrime[j] = false

**largestPrimeDivisor[j] = i**

j = j + i

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:

` primeDivisors = [empty list]`

while n > 1 :

append largestPrimeDivisor[n] to the end of primeDivisors

n = n / largestPrimeDivisor[n]

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(n-k+1, n-k+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 n-k+1 and n.

So, the solution will looks as follows:

- Calculate the prime factorization for each number between n-k+1 and n.
- Using it, find the maximal occurrence power for each prime from 2 to n, inclusively.
- The answer will be equal to the product of primes from 2 to n, each in its’ maximal occurrence power.

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 points

Let’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:

- D_1 = [1]
- D_2 = [1, 2]
- D_3 = [1, 2, 3]
- D_4 = [1, 1, 3, 4]

Suppose that D_{n-1} is constructed correctly. How do we get D_n using it?

For the beginning, let’s take D_n = D_{n-1} 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:

- First, we process all the positions from the corresponding stack that have the power of p less or equal to the power of p in n (i.e. the number of times that n can be divided by p without remainder). We divide these positions by p in their respective powers and pop them from stack. For example, if we have n=4, we will firstly have D_4=[1, 2, 3, 4]. But the stack of prime number 2 will have the information that at position 2, D_4[2] is divisible by 2. The power of 2 in 2 is obviously 1 and it is less than the power of 2 in the integer 4. So we divide D_4[2] by the power of 2 in 2 and remove the information that D_4[2] is divisible by 2 (because it is no longer divisible by 2). Finally, we get D_4 = [1, 1, 3, 4].
- Then, there can be an entry in the corresponding stack with the power of p greater that the power of p in n. In this case, we divide the value of D_n[] at that position by p in the power it occurs in n. This way, the sought invariant will be held.
- Finally, we add a new entry to the corresponding stack, containing the position n and the maximal power p in n.

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 Solution

Can be found here

# Tester’s Solution

Can be found here