Luogu7575 「PMOI-3」公约数

发表于 更新于 分类于 ， ， 阅读次数：

题意：给出 和一个长度为 的序列 ，保证 互不相同。

求

答案对 取模，，时限 。

直接推式比较吃力，限制呈一条链的形式，考虑 。

记 为：考虑了前 个数，且第 个填了 的方案数。

显然有转移：

使用反演：

预处理 ，上式即可 计算。

注意到 当 为 的倍数时才可能会有值，时间复杂度为 。

又因为 互不相同，故复杂度为 ，无法通过。

使用狄利克雷前缀和加速，复杂度变为 ，可以通过。