模数为奇数的时候,我们可以在某个环上绕圈

此时单独一个边是可以被记入方案里的,构造方法就是我们在一开始在u想要到达v,然后中间有 ( x , y ) (x,y) (x,y)一条边,那么我们只需要 u , x u,x u,x绕m次,最后一定停在x,然后走一步,然后 y , v y,v y,v绕m次走到v即可

那么我们考虑此时最优的一定是这些边,不需要绕任何一个环,我们所有边方案组合就能得到最优

而想要所有边我们只需要找到任意一个经过所有边若干次的路径就好了,然后再 m o d    m \mod m modm意义下假设我们有一个 G = gcd ⁡ ( x 1 . . x m , m ) G=\gcd(x_1..x_m,m) G=gcd(x1​..xm​,m),因此就有这一个很好的G了

于是对于一个可以表示出的值a,所有 a + k G m o d    m a+kG\mod m a+kGmodm都可以被表示出来了

我们假设现在就是所有的情况,考虑如何回答询问

对于某组询问,我们想知道的是诸如 x , x + b . . . x + ( c − 1 ) b x,x+b...x+(c-1)b x,x+b...x+(c−1)b是否都可以被表示出来

直接解似乎很愚蠢,我们考虑解 x + k b x+kb x+kb的k看看他满足什么条件

假设能够表示出 x + k b ≡ a ( m o d G ) x+kb\equiv a(mod G) x+kb≡a(modG)

那么我们简单移项变换就有

k b + y G = a − x kb+yG= a-x kb+yG=a−x

于是对于该方程使用扩展欧几里得就可以解出来了,解出最小满足条件的k,那么剩下的就是看k和c的交集是什么样的,相当于 k ′ = k 0 + x G ( G , b ) k'=k0+x\frac{G}{(G,b)} k′=k0+x(G,b)G​

等差数列求交?

我们已经解出来 k ′ k' k′然后直接看在 [ x , x + ( c − 1 ) b ] [x,x+(c-1)b] [x,x+(c−1)b]范围中的有多少个即可!这个就是等差数列的交集qwq

但是显然我们还有偶数

先考虑偶数的一条边如何算入答案,实际上他会被算入边权的两倍进去,即 g c d ( 2 k , m ) gcd(2k,m) gcd(2k,m)

我们可以考虑任意一条原来从 x x x到 y y y的道路,然后在这个道路的基础上把这两次加进去就好了

相当于我们可以在半途突然卷两次 ( x , y ) (x,y) (x,y)的路径,使得这个边被额外算入两次,而其余的我们不关心也不重要

此时发现我们至少要有一条原来从 x x x到 y y y的道路对吧,因此我们会发现上述加边构造也必须在这条道路的基础上加边

因此考虑如何维护这样一条道路:可以证明我们任意选择一条,都可以在这2w的边集合内增加增加拓展出所有其他的情况

比方说我们有 a − > b − > c − > d a->b->c->d a−>b−>c−>d且 a − > d a->d a−>d的四元环,那么我们会发现此时加入了 a − > d a->d a−>d这条边正好就导致了我们只记录了 ( a , b , w ) (a,b,w) (a,b,w)这个环的信息

然后我们比方说要变成 ( c , d , w ) (c,d,w) (c,d,w),那么只需要跑一遍 w , b , a , d , c w,b,a,d,c w,b,a,d,c,然后再a,b之间绕m-2次即可消除a,b两条边的贡献,环就变成了 ( w , a , b ) (w,a,b) (w,a,b)

有了这个结论之后,就相当于任意的一条路径为a,然后b为gcd的贡献,就变成了奇数中的上式,可以随意加入进去了

时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)