本文主要是介绍(FJWC2020) DTOJ 4690. 亚特兰大，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
司令部截获了深海的电报，你的镇守府即将被深海轰炸。
虽然你作为历战提督，已经有了很多局地战、火箭机，但是刚刚击破 E6 甲，拥有亚特兰大以及最高倍率对空 ci 的你，决定只用亚特兰大抵挡对面的炸家。
你的镇守府可以看成一棵树，深海的轰炸是在某两个点之间进行的（起点终点交换视为一种），轰炸路径是树上的简单路径。也就是说，深海一共有 C n 2 C_n^2 Cn2 种可能的轰炸方案。
你的亚特兰大在不同的边上具有不同的击坠值，最终深海剩下的飞机数是经过路径上所有击坠值的 g c d − 1 gcd-1 gcd−1。当这个值变成 0 0 0 时，你就成功抵挡住了深海的炸家。
现在你想知道，深海一共有多少种可能的轰炸方案，你可以成功抵挡。
但不幸的是，亚特兰大初来乍到，击坠值有点不稳定，所以会出现 Q Q Q 次击坠值变化，每次变化指某一条边的击坠值改变。
请你计算出这 Q + 1 Q+1 Q+1 种局面的所有答案。
对于所有数据，满足 2 ≤ n ≤ 1 0 5 , Q ≤ 100 , 1 ≤ w , x ≤ 1 0 6 2 \leq n \leq 10^5,Q \leq 100,1\leq w,x\leq 10^6 2≤n≤105,Q≤100,1≤w,x≤106。
对于 10 % 10\% 10% 的数据， n ≤ 300 n \leq 300 n≤300。
对于 30 % 30\% 30% 的数据， n ≤ 1000 n \leq 1000 n≤1000。
对于 70 % 70\% 70% 的数据， n ≤ 7000 n \leq 7000 n≤7000。
题解
先考虑没有修改怎么做，考场上写的是莫比乌斯反演后用点分治计算（因为是关于路径的计数），但效率是 O ( s n l o g n ) O(snlogn) O(snlogn)的，其中 s s s为约数个数（最大 240 240 240，去掉 m u = 0 mu=0 mu=0后最大 128 128 128），且常数大过不了。既然反演后每个因数是独立的，考虑每个因数单独计算，各自维护它的倍数的边组成的图，对每条边把它的因数的图对应的点连起来，用并查集维护即可，效率 O ( s n ) O(sn) O(sn)（我好弱智啊）。
注意到修改次数没有很多，即每次修改后对应的图，大部分边是一样的，如果每次仍重新计算很浪费。考虑先做完没有改过的边，对每一次修改，都加上有修改的 q q q条边，同时要支持可撤销（即恢复到原来状态），用启发式合并即可，效率 O ( q 2 l o g n ) O(q^{2}logn) O(q2logn)。
这篇关于(FJWC2020) DTOJ 4690. 亚特兰大的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
