牛客练习赛77官方题解（转载）（加上了公式）

转载至牛客练习赛77官方题解。

作者：Maddison10

由于那位出题人不会在牛客讨论区用mathjax，我来帮忙写一下。

A - 小G的sum

签到题，等差数列求和输出即可。

B - 小G的GCD

类似的思路，我们发现约数的条件我们也是可以转化成倍数的。
这样就是考虑的倍数在之内的数的求和，我们同样可以用等差数列求和来求出来。

C - 小G的约数

容易发现我们的这个函数。
这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件，因此还是转化成倍数问题。
于是这个我们其实可以用整除分块来优化。
推荐一个博客： 整除分块 - pengym。

D - 小G的LY数对

本题我们用一种折半思想类似折半的思想来做。
相当于我们枚举一位，然后另外一位用meeting in the middle做。
但是我们还需要减掉一些重复的情况，这个很好推导具体可以见代码。
于是我们发现这样我们就可以hash了。
但是这题我们的unorderedmap过不了，因此需要手写哈希。
时空复杂度：
注意hash的复杂度是的。

转载人补充：可以用基数排序真正去掉排序中的的复杂度。代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46873209。

E - 小G的GLS图

容易发现我们暴力建图跑割点正确性是对的。
因此我们下一步目标是如何优化建图。
显然，这道题 tarjan 算法是必须使用的。
tarjan 算法的复杂度就是图的大小。
我们发现可以在值域下手。
于是我们发现这个gcd和其他约数没有关系，我们只需要考虑质数。
显然这个范围是可以接受的。
因此我们每次像质因数连边，然后在无向图上缩点，判断强联通分量就可以了。
这样我们只需要对每个点的出边考虑就可以了。
但是我们需要注意的是要判断一下单独一个点的情况，很多人好像都WA在这里了。
容易发现我们建图后的规模是可以接受的。
时间复杂度或者。

F - 小G的排列

我们首先发现正着不好做，考虑到“不超过”这个限制太强了，我们把它容斥掉。首先长度不超过等价于没有长度为的，然后变成枚举位置使得满足条件。
然后我们可以分类讨论：
于是就是公差为的等差连续子序列。考虑两段限制区间叠在一起的情况，如果严格重合，那么显然公差相同；如果只有端点重合，由于这是一个排列，公差也只能相同。合并限制区间，让它们任意两个都不重合。
在这种情况下，设限制区间有个，不在限制区间里的有个，那么先把所有限制区间各看作一个数，排列所有数的相对大小，有种情况；再考虑限制区间的公差，有种情况。
因此我们记表示把前个点分成个限制区间和个无限制点的容斥系数和，表示在上述条件下作为限制区间末尾的容斥系数和。
初值
转移
答案
注意到在上述转移式中 jj 的需求不高。设

不难改写上述动态规划为：

初值
转移
答案

可以采用前缀和优化后时间复杂度，滚动数组优化后空间复杂度。

如有转载纰漏，请在评论区告诉我，谢谢。

与题目内容相关问题请在帖子牛客练习赛77官方题解中评论或联系出题人Maddison10。