CF571E Geometric Progressions
洛谷：CF571E Geometric Progressions
Codeforces：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\) 取模。
Solution
首先特判掉答案为某个 \(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}))}\)，进行下一次合并。
肯定不能直接存下 \(A, B\)，要手写一个类型存每种质因数的个数以及各种运算。次数会爆 int，但不会爆 long long。
简直可以称为 “扩展ExCRT”。实现可以参考 xht。
标签：le,CF571E,合并,AB,Progressions,Geometric From： https://www.cnblogs.com/Schucking-Sattin/p/17899737.html