牛客练习赛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
签到题，等差数列求和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
由于latex的原因在这里看吧orz
另外：撞了快艇下大雨我同学的验题账号，大家不要在意orz
代码：
美团成长空间 2791人发布