CF571E Geometric Progressions

Problem

给定 \(n\) 以及 \(n\) 个正整数对 \(a_i, b_i\)。
第 \(i\) 对 \(a_i, b_i\) 确定了一个序列 \(\{a_i, a_i b_i, a_i b_i^2, a_i b_i^3, \ldots \}\)。
询问最小的在 \(n\) 个序列中都有出现的数，或者判断不存在。
\(n \le 100\)，\(a_i, b_i \le {10}^9\)，答案对 \({10}^9 + 7\) 取模。

首先特判掉答案为某个 \(a_{i}\)。

否则，记 \(S(A)\) 表示 \(A\) 的本质不同质因数集合。

若 \(\exists 1 \le i < j \le n, S(a_{i}) \cup S(b_{i}) \neq S(a_{j}) \cup S(b_{j})\)，则无解。下记 \(P = S(a_{i}) \cup S(b_{i})\)。

假设最终答案的形式在每一组序列中表述为 \(a_{i}b_{i}^{k_{i}}\)。

从前往后合并每一组 \(a_{i}b_{i}^{k_{i}}\) 形式的限制，将合并完前若干组后的可行答案写成 最小表示 \(AB^{K}\)。

假设当前考察将 \(AB^{K}\) 与 \(a_{i}b_{i}^{k_{i}}\) 进行合并。

对每个 \(p \in P\) 分别考虑，记 \(c_{p}(A)\) 表示 \(A\) 唯一分解后包含的质因数 \(p\) 的个数。则可以列出 \(|P|\) 个方程：

\[\begin{aligned} c_{p}(a_{i}) + k_{i}c_{p}(b_{i}) = c_{p}(A) + Kc_{p}(B) \\ \end{aligned} \]

合并这 \(|P|\) 个方程，会出现如下结果：

在合并过程中判断无解。
可以直接解出 \(K\)，确定唯一的可行解，退出循环，并判断它是否能作为最后的答案。
否则最后只留下一个有效的不定方程 \(uK + vk_{i} = w\)，可以用扩展欧几里得算法算出最小可行 \(K\)（或最小可行 \(k_{i}\)。本质是取最小 \(W = AB^{K} = a_{i}b_{i}^{k_{i}}\)），使得 \(AB^{K} = a_{i}b_{i}^{k_{i}}\)。

然后考虑合并完后的答案表示为 \(A^{'}{B^{'}}^{K^{'}}\)。需有 \(A^{'}{B^{'}}^{K^{'}} = AB^{K}\times B^{x} = a_{i}b_{i}^{k_{i}} \times b_{i}^{y}\)。

取 \(A^{'} = AB^{K} = a_{i}b_{i}^{k_{i}}\)，\(B^{'} = \prod\limits_{p \in P}p^{\operatorname{lcm}(c_{p}(B), c_{p}(b_{i}))}\)，进行下一次合并。