Portal 不会写带权并查集+1 tutorial 额， 首先可以发现像树上最短异或路径一样， 对于每个联通块的求一个生成树， 对于每个环我们可以在走 ( u , v ) (u,v) (u,v)的树上路径的同时逃到这个环上走任意圈然后走回来。 而中间的路我们只需要重复走 m m m趟来回就可以看作没有贡献。 然后在 ( m o d m ) \pmod m (modm)的情况下，有一个长度为 k k k的环，我们就可以达到:树上路径长 + p g c d ( k , m ) +p \ gcd(k,m) +p gcd(k,m)的所有长度。 有多个环可以发现就是把 k k k变成他们的 g c d gcd gcd。 询问就是求一个同余方程的解数： p k ≡ x + i b ( m o d m ) ， i ∈ [ 0 , c − 1 ] pk \equiv x+ib \pmod m ， i \in [0,c-1] pk≡x+ib(modm)，i∈[0,c−1] （变量是 i i i） 一开始我 s b sb sb了。 其实这个方程很简单： 求出 x + i b ≡ 0 ( m o d k ) x+ib\equiv 0 \pmod k x+ib≡0(modk)的最小非负整数解 i 0 i_0 i0 然后就可以把特解每次 + k gcd ( k , b ) +\frac k{\gcd(k,b)} +gcd(k,b)k就可以得到下一个解， 除一下就可以得到解的个数。
A C C o d e \rm AC \ Code AC Code
#include<bits/stdc++.h> #define maxn 1000006 using namespace std; char cb[1<<15],*cs=cb,*ct=cb; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++) void read(int &res){ char ch; for(;!isdigit(ch=getc());); for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); } int n,m,q; int F[maxn]; int d[maxn],g[maxn]; int Find(int u){ if(!F[u]) return u; int t = F[u]; F[u] = Find(F[u]) , d[u] = (d[u] + d[t]) % m; return F[u]; } int gcd(int a,int b){ return !b ? a : gcd(b,a%b); } void exgcd(int a,int b,int &gcd,int &x,int &y){ if(!b) gcd=a,x=1,y=0; else exgcd(b,a%b,gcd,y,x), y-=(a/b)*x; } int main(){ // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); read(n),read(m),read(q); for(int i=1;i<=n;i++) g[i]=m; for(int op,u,v,x,b,c;q--;){ read(op),read(u),read(v),read(x); if(op == 1){ b=Find(u),c=Find(v); if(b == c) g[c]=gcd(g[c],abs(d[u]-d[v])+x); else F[b] = c , g[c] = gcd(g[c],g[b]) , d[b] = (1ll*x-d[u]-d[v]) % m; g[c]=gcd(g[c],x*2ll); } else{ read(b),read(c); // kg = x+ib -> ib = -x \pmod g if(Find(u) != Find(v)){ printf("%d\n",0); continue; } x = (x - 1ll * d[u] - d[v]) % m; if(b == 0){ if(x%g[Find(u)]==0) printf("%d\n",c); else printf("%d\n",0); continue; } int x1,x2,gd,gp=g[Find(u)]; exgcd(b,gp,gd,x1,x2); gp = gp / gd; if(x % gd != 0){ printf("0\n"); continue; } x1 = ((1ll * x1 * ((-x) / gd)) % gp + gp) % gp; if(x1<c) printf("%d\n",(c-x1+gp-1)/gp); else printf("0\n"); } } }