[NowCoder11253J]Product of GCDs

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

实际上只需要考虑 $pp$ 为质数的情况，但是对于 $p^2\mid \gcd p^2\backslash mid\backslash gcd$ （设有 ${\displaystyle \mathrm{ }{t}_2=\left(\genfrac{}{}{0px}{}{f_{p^2}}{\mathrm{ }k}\right)}\backslash displaystyle t\_2=\{f\_\{p^2\}\backslash choose k\}$ 个子集满足），${\displaystyle \mathrm{ }{p}^{\left(\genfrac{}{}{0px}{}{f_p}{\mathrm{ }k}\right)}}\backslash displaystyle p^\{f\_p\backslash choose k\}$ 只计算了 $(p^1{)}^{t_2}(p^1)^\{t\_2\}$ 的贡献，而实际上这部分贡献为 $(p^2{)}^{t_2}(p^2)^\{t\_2\}$ ，少算了 $p^{t_2}p^\{t\_2\}$ 。对于 $p^{c}p^c$ 也同理，归纳可得 $pp$ 的总贡献为 ${\displaystyle \sum \left(\genfrac{}{}{0px}{}{f_{p^c}}{\mathrm{ }k}\right)}\backslash displaystyle\backslash sum\{f\_\{p^c\}\backslash choose k\}$ 。 时间复杂度$O(\sqrt{\mathrm{ }}P+T\left({\displaystyle \frac{\sqrt{\mathrm{ }}P}{\log \mathrm{ }P}+\frac{x}{\log \mathrm{ }x}\log \mathrm{ }P+nk}\right))O\backslash left(\backslash sqrt P+T\backslash left(\backslash displaystyle\backslash frac\{\backslash sqrt P\}\{\backslash log P\}+\backslash frac\{x\}\{\backslash log x\}\backslash log P+nk\backslash right)\backslash right)$ 

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

代码