[Codeforces571E] Geometric Progressions

口胡的没实现过,如有错误请 QQ 或评论告诉我!

题解

考虑只有两个等比数列的情况。

第一个等比数列:\(a_1, a_1b_1, a_1b_1^2, \ldots\)

第二个等比数列:\(a_2,a_2b_2,a_2b_2^2,\ldots\)

假设 \(v\) 同时出现在两个等比数列中,那么 \(\exists k_1, k_2 \in \mathbb{N}, v = a_1b_1^{k_1} = a_2b_2^{k_2}\)

\(p_i\) 表示第 \(i\) 个素数。

\(b_1 = \prod p_i^{c_{1i}}, b_2 = \prod p_i^{c_{2i}}\)

考虑任意两个不同素数 \(p_i\)\(p_j\),假设 \(p_i\)\(a_1,a_2\) 中出现次数分别是 \(w_{1i},w_{2i}\)

那么有 \[ \begin{cases} k_1 c_{1i}+w_{1i} = k_2{c_{2i}} + w_{2i}\\ k_1 c_{1j}+w_{1j} = k_2{c_{2j}} + w_{2j} \end{cases} \] 这是一个二元一次方程组。假设 \((c_{1i},-c_{2i})\)\((c_{1j}, -c_{2j})\) 线性无关,这个方程组有唯一解。

假设存在 \(i < j\)\((c_{1i},-c_{2i})\)\((c_{1j}, -c_{2j})\) 线性无关,那么解出这个方程。这样就得到了唯一一个可能是所有等比数列共有元素的数(的素因数分解),然后检验一下即可。

否则,对于任意的 \(i < j\) 都有 \((c_{1i},-c_{2i})\)\((c_{1j}, -c_{2j})\) 线性相关。

那么存在正整数 \(w\)\(b_1 = w^{i_1}, b_2 = w^{i_2}((i_1,i_2) = 1)\)\[ a_1b_1^{k_1} = a_2b_2^{k_2} \Leftrightarrow w^{k_1i_1-k_2i_2}=\frac {a_2} {a_1} \] 不妨设 \(a_1 \le a_2\)。那么一定有 \(a_1 \mid a_2\)

\(\frac {a_2} {a_1} = x\),如果有解,必有 \(x = w^n, n \in \mathbb{N}\)

方程变为 \(k_1i_1-k_2i_2 = n\)

这是一个简单的不定方程。不难找到这个方程的一组解 \(k_1= x, k_2 = y\)。(具体来说先找到 \(k_1i_1-k_2i_2=1\) 的解,然后在两边乘以 \(n\)

那么这个方程的通解为 \(k_1 = x + pi_2, k_2 = y + pi_1, p \in \mathbb{Z}\)

不难找到 \(k_1\) 最小的非负整数解,假设这时 \(a_1w^{k_1c_1}=t\)。这样两个等比数列就被合并为了一个等比数列:\(t, w^{i_1i_2}t,w^{wi_1i_2}t,\ldots\)

继续把合并得到的等比数列和其他等比数列进行相同的操作即可。