Official

E - LCM on Whiteboard Editorial by en_translator


Prime Factorization and Least Common Multiple (LCM)

In this problem, the prime factorizations of \(a_i\) are given. While we leave the explanation of prime factorizations itself to schoolbooks and articles, we will describe some prerequisites regarding the properties.
First, for a positive integer \(x\), consider the index of \(p\) in the prime factorization of \(p\); let us simply call the index the \(p\)-adic order of \(x\). For example, the \(2\)-adic order of \(20=2^2 \times 5\) is \(2\) and its \(5\)-adic order is \(1\). Moreover, if a prime \(p\) does not appear in the prime factorization of an integer, let its \(p\)-adic order be \(0\). For example, the \(3\)- and \(998244353\)-adic orders of \(20\) are \(0\).
Considering the prime factorization, a positive integer \(x\) is a multiple of a positive integer \(y\) if and only if “for all prime \(p\), the \(p\)-adic order of \(x\) is greater than or equal to the \(p\)-adic order of \(y\).” Also, the LCM of positive integers \(x_1,\ldots,x_k\) are such positive integer that for all prime \(p\), the \(p\)-adic order of the integer is “the maximum \(p\)-adic order of \(x_1,\ldots,x_k\).”

Representation of Positive Integers with Associative Arrays

The answer to this problem can be obtained by finding the LCMs \(L_1,\ldots,L_N\) when \(a_i\) is replaced by \(1\) for \(i=1,\ldots,N\), but this way, the execution time will exceed the time limit.
First, consider the following issue.

  • \(a_i\) and \(L_i\) can be so enormous that it does not fit in a \(64\)-bit integer type, or even exceed the memory limit (for example, \(a_1\) in Sample Input 2 alone occupies nearly 4 GB of memory).

On the other hand, we can manage \(a_i\) with an associative array whose keys are primes and whose values are the orders (where we can ignore the infinite number of primes of which orders are \(0\)), and when computing \(L_i\), find the \(\max\) for each key of the associative array, so that the positive integers are handled within somewhat realistic size of memory.

Improvement to Quasi-Linear Time

For more improvement, consider the condition that \(L \neq L_i\), where \(L\) is the LCM of all \(a_1,\ldots,a_N\). As we find \(\max\) for each key when computing the LCM, \(L \neq L_i\) holds if and only if there exists prime \(p\) such that “the \(p\)-adic order of \(a_i\) is equal to the \(p\)-adic order of \(L\), and there is no \(j (\neq i)\) such that the \(p\)-adic order of \(a_j\) is equal to that of \(L\).” Also, since the \(p\)-adic order of \(L_i\) is strictly less than that of \(L\) (and there is no \(j\) such that the \(p\)-adic order of \(a_j\) is equal to that of \(L\)), \(L_i \neq L_j(i \neq j)\).
Therefore, considering the case where \(L=L_i\), the answer is found as \(\min (c+1,N)\), where \(c\) is the number of \(i\) such that \(L \neq L_i\).
In the value of the associative array representing \(L\), maintain not only the \(p\)-adic order but also the number of \(i\) that achieves that order, so that we can determine if \(L \neq L_i\) fast enough for each \(i\) in a total time complexity of \(\mathrm O(\sum{m_i} \log \sum{m_i})\) (where the operations on associative arrays are assumed to be logarithmic).

posted:
last update: