Linear Congruential Generator
Contest: Technocup 2019 - Elimination Round 1
Difficulty rating: 2900
Tags: number theory

You are given a tuple generator $$$f^{(k)} = (f_1^{(k)}, f_2^{(k)}, \dots, f_n^{(k)})$$$, where $$$f_i^{(k)} = (a_i \cdot f_i^{(k - 1)} + b_i) \bmod p_i$$$ and $$$f^{(0)} = (x_1, x_2, \dots, x_n)$$$. Here $$$x \bmod y$$$ denotes the remainder of $$$x$$$ when divided by $$$y$$$. All $$$p_i$$$ are primes.

One can see that with fixed sequences $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ the tuples $$$f^{(k)}$$$ starting from some index will repeat tuples with smaller indices. Calculate the maximum number of different tuples (from all $$$f^{(k)}$$$ for $$$k \ge 0$$$) that can be produced by this generator, if $$$x_i$$$, $$$a_i$$$, $$$b_i$$$ are integers in the range $$$[0, p_i - 1]$$$ and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by $$$10^9 + 7$$$

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the tuple.

The second line contains $$$n$$$ space separated prime numbers — the modules $$$p_1, p_2, \ldots, p_n$$$ ($$$2 \le p_i \le 2 \cdot 10^6$$$).

Output format:
Print one integer — the maximum number of different tuples modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example we can choose next parameters: $$$a = [1, 1, 1, 1]$$$, $$$b = [1, 1, 1, 1]$$$, $$$x = [0, 0, 0, 0]$$$, then $$$f_i^{(k)} = k \bmod p_i$$$.

In the second example we can choose next parameters: $$$a = [1, 1, 2]$$$, $$$b = [1, 1, 0]$$$, $$$x = [0, 0, 1]$$$.

Example input:
4
2 3 5 7

Example output:
210

Example input:
3
5 3 3

Example output:
30

Editorial:
Each generator $$$f_i^{(k)}$$$ can be represented as functional graph so the number of different values equal to the legth of the cycle $$$c$$$ plus the length of pre-period $$$pp$$$. Generalizing on tuples leads to next observation: number of different tuples equals to $$$\max\limits_{i = 1..n}(pp_i) + \mathop{\text{lcm}}\limits_{i = 1..n}(c_i)$$$.
Let's take a look at some generator $$$f_i$$$ to find out its possible $$$c_i$$$ and $$$pp_i$$$. If $$$a_i = 0$$$ then $$$f_i = x_i, b_i, b_i, b_i, \dots$$$. the $$$c_i = 1$$$ and $$$pp_i = 0$$$ or $$$pp_i = 1$$$. If $$$a_i = 1$$$ then $$$f_i^{(k)} = (x_i + (k - 1) b_i) \mod p_i$$$. Since $$$p_i$$$ is a prime then $$$c_i = 1$$$ or $$$c_i = p_i$$$ and $$$pp_i = 0$$$.
If $$$a_i > 1$$$ then exists $$$a_i^{-1}$$$ and $$$(a_i - 1)^{-1}$$$, thus $$$pp_i = 0$$$. Since there is not pre-period we need to find minimal positive $$$k$$$ such that $$$$$$x_i \equiv a_i^k x_i + b_i \sum\limits_{j = 0}^{k-1}{a_i^j} \Leftrightarrow x_i \equiv a_i^k x_i + b_i (a_i^k - 1) \cdot (a_i - 1)^{-1} \Leftrightarrow (a_i^k - 1) x_i + b_i (a_i^k - 1) \cdot (a_i - 1)^{-1} \equiv 0 \\ \Leftrightarrow (a_i^k - 1) (x_i + b_i \cdot (a_i - 1)^{-1}) \equiv 0 \mod p_i.$$$$$$
Since $$$p_i$$$ is a prime if $$$a \cdot b \equiv 0$$$ then $$$a \equiv 0$$$ or $$$b \equiv 0$$$. So if $$$(x_i + b_i \cdot (a_i - 1)^{-1}) \equiv 0$$$ and since it doesn't depend on $$$k$$$ then $$$k = 1$$$, so $$$c_i = 1$$$ and $$$pp_i = 0$$$. Otherwise, $$$(a_i^k - 1) \equiv 0$$$ and by Lagrange's theorem $$$k \mid (p_i - 1)$$$. Finally, since $$$p_i$$$ is a prime there exist $$$a_i$$$ such that $$$k = p_i - 1$$$.
At the end we can understand that only three cases are matter: $$$(c_i = 1, pp_i = 1)$$$, $$$(c_i = p_i, pp_i = 0)$$$ and $$$(c_i = p_i - 1, pp_i = 0)$$$.
Here some greedy ideas works: it always optimal try at first $$$(p_i, 0)$$$, then $$$(p_i - 1, 0)$$$ and only then $$$(1, 1)$$$; we can process elements in the descending order. But there is one problem: since we maximaize $$$\max\limits_{i = 1..n}(pp_i) + \mathop{\text{lcm}}\limits_{i = 1..n}(c_i)$$$ then there are cases, where we can make $$$\max\limits_{i = 1..n}(pp_i) = 1$$$ without lowering $$$\mathop{\text{lcm}}\limits_{i = 1..n}(c_i)$$$. Here comes two approaches:
The first solution (hard to prove correctness, the proven complexity):
Let's add to some structure $$$p_i$$$ in non ascending order: let's maintain $$$\text{lcm}$$$ as pairs: maximal power of prime $$$a_j$$$ and number of maximums $$$cnt_j$$$ for each prime number up to $$$2 \cdot 10^6$$$ .
For each $$$p_i$$$ we will try to add it as $$$p_i$$$ to the $$$\text{lcm}$$$. If this structure already have $$$p_i$$$ then we will add it as $$$p_i - 1$$$, so we need factorization of $$$p_i - 1$$$.
After that we will iterate over all $$$p_i$$$ again and check "can we remove it from structure without decreasing $$$\text{lcm}$$$". We will check it in the next way: for index $$$i$$$ just check for each prime divisor $$$pd_j$$$ of $$$p_i - 1$$$ if it was added as $$$p_i - 1$$$ (or of $$$p_i$$$ if it was added as $$$p_i$$$) is it true that ($$$a_{pd_j}$$$ > power of $$$pd_j$$$) or ($$$a_{pd_j}$$$ = power of $$$pd_j$$$ and $$$cnt_{pd_j} > 1$$$).
If we can remove some index $$$i$$$ so we can make $$$\max(pp_i) = 1$$$ — profit. Otherwise, it's impossible to get $$$\max(pp_i) = 1$$$. Here should be proof of correctness, but it is quite complicated (but I proved this solution to KAN and he agreed (hm, notorious coincidence)).
At the end, we need factorization of all numbers up to $$$2 \cdot 10^6$$$ it can be done with Sieve of Eratosthenes if we will remember minimal divisor for each number. So, the result complexity is $$$O((n + MAX) \log(n))$$$.
The second solution (the proven correctness, hard to prove the complexity):
Let's maintain same structure for $$$\text{lcm}$$$ but with some modification: we don't need $$$cnt_j$$$ but for each prime we will have a flag $$$mark_j$$$ — does this prime is occupied by $$$p_i$$$ from the input. Now, let's get to know a way to add arbitrary prime $$$p_i$$$ from the input to this structure. Name this function as $$$insert(v)$$$. If the structure doesn't have $$$v$$$ — just add it (recalc $$$a_v$$$ and $$$mark_v$$$ flag). Otherwise, we'll move to $$$v - 1$$$ and for each prime divisor $$$pd_k$$$ of $$$v - 1$$$ we'll try to update $$$pd_k$$$ in the structure — final trick is next: if we update $$$pd_k$$$ which have $$$mark_{pd_k}$$$ we will unmark it call a $$$insert(pd_k)$$$ recursively.
Now we can insert some $$$p_i$$$. We will at first find maximum $$$a_j$$$ for each prime. Then we will make $$$n$$$ quieries — calculate $$$\text{lcm}$$$ without $$$p_i$$$. This queries can be processed with dynamic connectivity. Final question is to evaluate number of operation done by $$$insert(v)$$$. We can limit it with number of prime divisors of all different primes we can reach from each $$$v$$$ up to $$$2 \cdot 10^6$$$. It was less than $$$D = 30$$$.
So result complexity is $$$O(n \log(n) \cdot D)$$$.
P.S.: Main correct is the second solution.