Elections in Saransk (easy version)

Observation 1: Decode the condition

In the easy version, $x=1$, so an ideal vote means

$$\mathrm{lcm}(p_1,p_2,\ldots,p_n)=p_1p_2\cdots p_n.$$

Look at one fixed prime $r$. Let $v_r(y)$ be the exponent of $r$ in $y$. Then

$$v_r(p_1p_2\cdots p_n)=\sum_{i=1}^{n} v_r(p_i),$$

but

$$v_r(\mathrm{lcm}(p_1,p_2,\ldots,p_n))=\max_{1\le i\le n} v_r(p_i).$$

Therefore we need

$$\sum_{i=1}^{n} v_r(p_i)=\max_{1\le i\le n} v_r(p_i)$$

for every prime $r$.

The values $v_r(p_i)$ are nonnegative integers. A sum of nonnegative integers equals their maximum iff at most one of them is nonzero. Translation: no prime may appear in two different chosen numbers. Equivalently, the chosen numbers $p_i$ are pairwise coprime. That is the whole damn problem.

Observation 2: Count choices per prime

Fix a prime $r$. Suppose $a_i$ contains $r$ with exponent

$$c_i=v_r(a_i).$$

In a valid voting array, prime $r$ has only these possibilities:

• nobody uses $r$: $1$ way;
• exactly one voter $i$ uses $r$: then its exponent in $p_i$ can be any of $1,2,\ldots,c_i$, giving $c_i$ ways.

So the number of choices for this prime is

$$1+\sum_{i=1}^{n} v_r(a_i).$$

Different primes are independent. Once every prime chooses its owner and exponent, each $p_i$ is determined as the product of prime powers assigned to voter $i$, and automatically $p_i \mid a_i$. Conversely, every valid array $p$ gives exactly one such set of per-prime decisions. Clean bijection, no gremlins hiding under the carpet.

Thus the answer is

$$\prod_{r} \left(1+\sum_{i=1}^{n} v_r(a_i)\right) \bmod 10^9+7,$$

where the product is over primes appearing in at least one $a_i$.

Implementation

Precompute the smallest prime factor $spf[y]$ for all $y\le 5\cdot 10^5$.

For each test case:

1. Factor every $a_i$ using $spf$.
2. For every prime factor $r$ with multiplicity $e$, add $e$ to $cnt[r]$.
3. Store touched primes so we can later multiply only relevant primes and reset them cheaply.
4. Output

$$\prod_{r\in touched} (cnt[r]+1) \bmod 10^9+7.$$

If all $a_i=1$, no prime is touched, and the empty product is $1$, which is correct: everyone must vote $1$.

Complexity

Let $A=5\cdot 10^5$. The sieve costs $O(A)$. Factoring all numbers costs $O(\sum n\log A)$ in the simple bound, easily fine for $\sum n\le 10^5$.

Memory usage is $O(A)$.