牛客练习赛77官方题解
T1
签到题，等差数列求和O(1)输出即可
T2
类似的思路，我们发现约数的条件我们也是可以转化成倍数的
这样就是考虑x的倍数在n之内的数的求和，我们同样可以用等差数列求和来求出来
T3
容易发现我们的这个函数G(n)=sum i=1..n i*n/i
这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件，因此还是转化成倍数问题
于是这个我们其实可以用整除分块来优化
推荐一个博客：https://www.cnblogs.com/peng-ym/p/8661118.html
T4
本题我们用一种折半思想类似折半的思想来做
相当于我们枚举一位，然后另外一位用meeting in the middle做
但是我们还需要减掉一些重复的情况，这个很好推导具体可以见代码
于是我们发现这样我们就可以hash了
但是这题我们的unorderedmap过不了，因此需要手写哈希。
时空复杂度：O(N*30)
注意hash的复杂度是O(1)的
T5
容易发现我们暴力N^2建图跑割点正确性是对的
因此我们下一步目标是如何优化建图
显然，这道题 tarjan 算法是必须使用的。
tarjan 算法的复杂度就是图的大小。
我们发现可以在值域下手
于是我们发现这个gcd和其他约数没有关系，我们只需要考虑质数
显然这个范围是可以接受的
因此我们每次像质因数连边，然后在无向图上缩点，判断强联通分量就可以了
这样我们只需要对每个点的出边考虑就可以了
但是我们需要注意的是要判断一下单独一个点的情况，很多人好像都WA在这里了
容易发现我们建图后的规模是可以接受的
时间复杂度O(Nsqrt(N))或者O(N log N)
T6
我们首先发现正着不好做，考虑到“不超过 ”这个限制太强了，我们把它容斥掉。首先长度不超过
等价于没有长度为
的，然后变成枚举位置
使得
满足条件。
然后我们可以分类讨论：
于是就是公差为 的等差连续子序列。考虑两段限制区间叠在一起的情况，如果严格重合，那么显然公差相同；如果只有端点重合，由于这是一个排列，公差也只能相同。合并限制区间，让它们任意两个都不重合。
在这种情况下，设限制区间有 个，不在限制区间里的有
个，那么先把所有限制区间各看作一个数，排列所有数的相对大小，有
种情况；再考虑限制区间的公差，有
种情况。
因此我们记 表示把前
个点分成
个限制区间和
个无限制点的容斥系数和，
表示在上述条件下
作为限制区间末尾的容斥系数和。
初值$$
转移$$
答案$$
注意到在上述转移式中 的需求不高。设
不难改写上述动态规划为：
初值$$
转移$$
答案$$
可以采用前缀和优化后时间复杂度 滚动数组优化后空间复杂度
.
