CF2034H Rayan vs. Rayaneh

ForgotMe · 2024-12-01 17:01:49 · 题解

很棒的一个题目啊。如果你尝试往线性代数方面去想的话，反而可能会被卡住，因为这个题的组合系数要求是整数意义下，与平常线代学习的内容有所不同。

首先思考对于一个确定的集合 S=\{x_1,x_2,\cdots,x_n\}，如何判断其是线性无关的。

形式化的将其写成方程，那就是对于 \forall i，整数意义下的不定方程 \sum_{j\ne i}c_jx_j=x_i 无解，根据裴蜀定理，可以知道其无解的充要条件就是 \gcd_{j\ne i}\{x_j\}\nmid x_i。

但是这个条件并不好直接刻画，考虑转化条件 \gcd_{j\ne i}\{x_j\}\nmid x_i，其等价于 \exist p_i^{q_i}，满足 p_i^{q_i}\nmid x_i，且 p_i^{q_i}\mid x_j(j\ne i)。这个条件不太直观，用文字来描述就是存在一个质数 p 满足 p 在 x_i 中的幂次是严格最小的！显然如果不存在这样的一个质数 p，那么一定会有 \gcd_{j\ne i}\{x_j\}\mid x_i。

于是就可以反过来思考了，如果现在已知每个数对应的这个质数的幂次 p_i^{q_i}，能不能找到一组合法的 x 呢？令 G=p_1^{q_1}p_2^{q_2}\cdots p_n^{q_n}，那么有解当前仅当 f_{\frac{G}{p_i^{q_i}}}>f_G，其中 f_x 表示 a 中是 x 的倍数的个数。

剩下的部分就很好做了，考虑令 M 为值域，p_1^{q_1}<p_2^{q_2}<\cdots <p_n^{q_n}，在 n>2 的情况下，显然会有 p_1^{q_1}<\sqrt{M}，且 \frac{G}{p_1^{q_1}}\le M，否则 f_{\frac{G}{p_1^{q_1}}} 一定是 0，那么就会无解。

于是直接枚举 p_1^{q_1},\frac{G}{p_1^{q_1}} 检查是否有解即可，注意在 \sqrt{M} 以内质数的幂次数量级别根据积分可知是 \mathcal{O}(\frac{\sqrt{M}}{\log M}) 级别的，于是总复杂度就是 \mathcal{O}(T\frac{M\sqrt{M}K}{\log M}+TnK+TM\log M) 的，其中 K 是答案的大小级别，根据上述推导可知，K 不可能超过 6，因为 2\times 3\times 5\times 7\times 11\times 13\times 17>10^5。

注意要加一些剪枝，不然会跑的很慢，不知道根号级别，开 100 组数据是怎么想的。

放个代码：https://www.luogu.com.cn/paste/q7q1oaik 。