考虑直接枚举 gcd⁡=p\gcd=p ，枚举倍数统计出 fp=∑[p∣ xi]f_p=\displaystyle\sum[p\mid x_i] ，那么 p∣gcd⁡p\mid\gcd 方案数即为  (fp k)\displaystyle {f_p\choose k} ，考虑容斥，去除 gcd⁡=tp\gcd=tp 的情况，减去这部分答案，即  (fp k)−∑(ftp k)\displaystyle {f_p\choose k}-\sum{f_{tp}\choose k} ，答案即  p(fp k)−∑(ftp k)\displaystyle p^{{f_p\choose k}-\sum{f_{tp}\choose k}}。预处理  P\sqrt P 内的质数，然后求出 φ(P)\varphi(P) 使用欧拉降幂即可，并且由于 kk 很小，所以可以直接 O(nk)O(nk) 暴力杨辉三角求组合数。 时间复杂度 O( P+T( Plog⁡ P+xlog⁡ P+nk))O\left(\sqrt P+T\left(\displaystyle\frac{\sqrt P}{\log P}+x\log P+nk\right)\right) 

实际上只需要考虑 pp 为质数的情况，但是对于 p2∣gcd⁡p^2\mid\gcd （设有  t2=(fp2 k)\displaystyle t_2={f_{p^2}\choose k} 个子集满足）， p(fp k)\displaystyle p^{f_p\choose k} 只计算了 (p1)t2(p^1)^{t_2} 的贡献，而实际上这部分贡献为 (p2)t2(p^2)^{t_2} ，少算了 pt2p^{t_2} 。对于 pcp^c 也同理，归纳可得 pp 的总贡献为 ∑(fpc k)\displaystyle\sum{f_{p^c}\choose k} 。 时间复杂度O( P+T( Plog⁡ P+xlog⁡ xlog⁡ P+nk))O\left(\sqrt P+T\left(\displaystyle\frac{\sqrt P}{\log P}+\frac{x}{\log x}\log P+nk\right)\right) 

虽然实际上在 PP 比较小的时候会因为没有 +φ(P)+\varphi(P) 导致答案错误，但是题目中 PP 有个较大的下限所以不影响。

代码