牛客挑战赛 47 题解

出了一些小锅，向大家道歉……

• A 的题面出了些问题。
• 评测机太快把 F 暴力放过去了……我自己写的暴力都会 T 所以以为没事，但大家常数确实优秀
• 本场比赛所有题目时限都在标程两倍以上（除了 F），G std 900ms 开了 2s，E 验题人 1.2s，std 2.6s 所以开的 4s，但好像确实有选手被卡常，非常抱歉

以下是题解。

T1：一道 GCD 问题

求出差分数组的 GCD，这个 GCD 就是原数组的 GCD 的最大可能值。只需要让 是这个数的倍数就能取到最值。

T2：又一道 GCD 问题

对每个 ，枚举其约数 ，。选 个的答案为 大于等于 的最大的 。直接做是 ，可以优化到 。

T3：条件

可能存在的边假如全都存在时都还不可能 那么 一定不能走到 ，否则就有可能可以。用 bitset 优化，。

T4：Lots of edges

所有满足起点的权值、终点的权值相同的都是本质相同的，可以合并计算。这样，本质不同的边只有 条，可以直接枚举。用枚举补集子集的方法即可不重复不遗漏。
最后用 BFS 计算答案即可。一个易错点在于要特判 的情况，若 输出 ，若 输出 ，若 且 且 有边连出则输出 ，否则输出 。复杂度 。

T5：路径

点分治求长度 的路径条数再前缀和然后二分回答询问。然后发现每轮的答案统计是卷积，可以用 NTT 实现。模数需要选取得足够大才能保证正确性。复杂度 。（ 为所有边权之和）

T6：简单题

可以把积性函数拆开（，因此 互质）莫比乌斯反演，最后得到的式子可以 暴力算。容易用 Dirichlet 前缀和优化到 。

T7：子串

• 法一：对 S 建 SAM、T 建PAM，SAM 上线段树合并维护转移边，PAM 上倍增预处理父亲。对于每个 T 的位置 i，找到 PAM 上 i 的节点和结尾为 i 的与 S 匹配的最大长度 now，用倍增找到 PAM 上最深的 x，满足 len[x]<=now，用 len[x] 更新答案。时间复杂度 。
• 法二：对 S,T 都建 PAM，然后在 PAM 上线段树合并，求最长公共路径。复杂度同上。