【题解】牛客挑战赛47

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

以下是题解。

## T1：一道 GCD 问题

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

## T2：又一道 GCD 问题

对每个 $a_i$，枚举其约数 $j|a_i$，$cnt[j]++$。选 $k$ 个的答案为 $cnt[j]$ 大于等于 $k$ 的最大的 $j$。直接做是 $O(n\sqrt{a_i})$，可以优化到 $O(a_i log a_i)$。

## T3：条件

可能存在的边假如全都存在时都还不可能 $i\to j$ 那么 $i$ 一定不能走到 $j$，否则就有可能可以。用 bitset 优化，$O(\dfrac{n^3}{w})$。

##T4：Lots of edges

所有满足起点的权值、终点的权值相同的都是本质相同的，可以合并计算。这样，本质不同的边只有 $O(3^17)$ 条，可以直接枚举。用枚举补集子集的方法即可不重复不遗漏。
最后用 BFS 计算答案即可。一个易错点在于要特判 $a_i=a_S$ 的情况，若 $i=S$ 输出 $0$，若 $a_S=0$ 输出 $1$，若 $i\ne S$ 且 $a_i\ne 0$ 且 $S$ 有边连出则输出 $2$，否则输出 $-1$。复杂度 $O(3^{17}+n)$。

## T5：路径

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

## T6：简单题

可以把积性函数拆开（$\mu(ij)\ne 0$，因此 $i,j$ 互质）莫比乌斯反演，最后得到的式子可以 $O(n \log n)$ 暴力算。容易用 Dirichlet 前缀和优化到 $O(n \log\log n)$。

## T7：子串

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