正文
失控的未来交通工具 （LOJ 508，带权并查集，数论）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
LOJ 508 失控的未来交通工具 （带权并查集 + 数论）
$ solution: $
很综合的一道难题。看了让人不知所措，数据范围又大，题目描述又不清晰。只能说明这道题有很多性质，或者很多优化。
好了，回来讲正解。像这种在图上寻找路径，并且对路径取模，尤其还不是简单路径的题，基本上都和环的性质有关。因为环我们可以无限跑啊！而这一道题在环上路径长度取模，需要联系到一个结论（就是天天爱跑步）：我可以加一个数 $ w $ 无限次，得到的数要对 $ m $ 取模，那么我最终 能且仅能 得到所有小于 $ m $ 的 $ gcd(w,m) $ 的倍数。知道了这个结论，本题就只需要再讨论三个问题了：
1. 当模数为奇数时：（这个不算正解一部分，只能有开导作用）
当 $ m $ 是个奇数时，我们可以在某条环上绕圈（注意单独的一条边也算环，因为我们可以来回跑）。对于某条长度为 $ w $ 的边 $ (x,y) $ ，如果我们想只让这一条边/环计入贡献，我们可以这样操作：（设询问里起点为 $ u $ 终点为 $ v $ ）在 $ u, x $ 之间来回跑 $ m $ 次，然后 $ (x,y) $ 只跑一次，然后再在 $ y,v $ 之间跑 $ m $ 次。这样我们两边的长度因为取模被削去，只留下那中间一条边的贡献！
于是我们通过这条边能走的长度一定是 $ gcd (m, w) $ 的倍数。设 $ u,v $ 所在连通块有 $ k $ 条边，那么走的路径一定是 $ G = gcd (m, w_1 , w_2 , w_3 , ... ,w_k) $ 的倍数。于是我们开一个并查集维护连通块的 $ gcd $ 就好。当然我们首先还需要得到随便一条可以从 $ u $ 出发走到 $ v $ 的路径得长度，再从这个长度上添加或消除边的贡献，这个我们也可以用带权并查集维护。
2. 如何处理回答的信息
$ upd: $ 经 $ LYH $ 大佬的提醒，现将本段一些错误更新。
题目意思大致：我们有一条路径 $ (u,v) $ ，询问在 $ x, x + b, ... , x + (c − 1)\times b $ 这些数中，有多少数在原图上存在一条从 $ u $ 到 $ v $ 的路径，使得这个数和路径长度模 $ m $ 同余。
首先上面我们说了，我们用并查集维护一个值（暂时叫 $ G $ ），所有为 $ G $ 的倍数长度的路径我们都可以走到，于是题目所求就变成了： 在 $ x, x + b, ... , x + (c − 1)\times b $ 这些数中，有多少数存在一条路径，使得这个数和这条路径长度的差是 $ G $ 的倍数。 （注意是差值）
可以知道当 $ c $ 很大的时候，我们肯定不能暴力判断。我们分析性质发现给出的数列是一个等差数列。所以这个数列在模 $ G $ 意义下一定是循环的，所以只需要找到第一个模 $ G $ 等于0的位置（就是说这个数是 $ G $ 的倍数）与循环节长度即可。即要求解同余方程 $ x + k\times b ≡ d[u]+d[v] ~~(mod~G) \quad -> \quad k\times b~+ y\times G = d[u]+d[v]-x $ 中 $ k $ 的值，这个用扩展欧几里得就好。而为了更契合扩展欧几里得，博主在代码里将这个同余方程的系数用 $ A,B,C $ 表示。
rg A=b,B=g[fx],G=gcd(A,B),C=(ll)d[u]+d[v]-w+B; //列出同余方程的系数
// 同余方程： C - x*A ≡ 0 (mod B) -> x*A + y*B = C (对应上文第二个式子！)
if(C%G){puts("0"); continue;} //方程无解，请参见扩欧的做法
rg x,y; A/=G; B/=G; C/=G; //请参见扩欧的解方程的步骤
exgcd(A,B,x,y); x=((ll)x*C%B+B)%B; //解出同余方程
if(x<c)ans=(c-1-x)/B+1; //注意我们找的是x的最小解，循环长度是模数B！ （同余方程性质）
printf("%d\n",ans); //输出答案
3. 当模数为偶数：（这里才是正解）
这种情况可以用与奇数相似的做法，但是比奇数复杂得多！当 $ m $ 是个偶数时，我们可以在某条环上绕圈，但是我们绕 $ m $ 次之后会回到原点，这代表着我们只能得到 $ gcd(m,2\times w) $ 的倍数的路径长度（好好理解，这个需要自己思考），这个贡献和跑一遍含有这条边的环的贡献 $ gcd(m,k+m) $ 可能不一样！
所以我们考虑另一种做法：首先，我们依旧要维护边的贡献 $ gcd(m,2\times w) $ ，然后考虑将环的贡献也加进去。这个我们只要在并查集合并时维护，只有当两个节点同属于一个联通块时我们加入这条边才会产生环。然后我们只要维护 这两个点到并查集的根的路径加上这条边产生的环 的贡献即可。（以下图为例）我们此时并查集里根为1号结点，我们现在加入 $ w $ 边，我们只要维护 $ (a,b,w) $ 形成的环即可。虽然 $ w $ 边还可以和 $ (c,d) $ 形成环，但是我们之后也可以这样操作使的两个环相互转换：从2号结点跑环 $ w,a,b $ 回到2节点，再跑 $ (c,d,a,b) $ 回到2节点，这时 $ (a,b) $ 两条边跑了两次我们只要再 $ (a,b) $ 来回跑 $ m-2 $ 次即可消去 $ (a,b) $ 两边的的贡献，将环变成 $ (w,d,c) $ 。
同理我们还可以实现 $ (w,a,b) $ 到 $ (a,b,c,d) $ 环的转化，这里不做多讲，不会可以直接留言。这种联通块里加入边的贡献我们可以这样记录： $ G=gcd(G,d[u]+d[v]+w,2\times w) $ ，其中第一个是联通块原贡献值，第二个是包含 $ w $ 边的环的贡献，第三个是 $ w $ 这条边单独的贡献（在最开始讲了）。
于是我们用带权并查集维护节点间随意某一条路径，再从这个长度上用上述方法添加或消除环和边的贡献，这样可以得到一个合并后的总贡献 $ G $ 的所有倍数的路径长度。然后我们直接再按照第二个问题的做法做就可以了！
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,q;
int d[1000005]; //并查集里面节点到其联通块的根的距离
int g[1000005]; //当前联通块的gcd，如天天爱跑步
int fa[1000005]; //并查集
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline int gcd(int a,int b){
if(b==0)return a; return gcd(b,a%b);
}
inline int getfa(int x){
if(x==fa[x])return x;
rg to=getfa(fa[x]); //注意顺序，防止信息被覆盖
d[x]=(d[x]+d[fa[x]])%m; //更新当前节点到根的距离
return fa[x]=to; //最后再赋值
}
inline void exgcd(int a,int b,int &x,int &y){ //扩展欧几里得
if(b==0) x=1,y=0; //直接构造一组解
else exgcd(b,a%b,y,x),y-=a/b*x; //我们不需要求gcd，只要解方程就好
}
int main(){
n=qr(); m=qr(); q=qr();
for(rg i=1;i<=n;++i) fa[i]=i,g[i]=m;
for(rg i=1;i<=q;++i){
rg op=qr(),u=qr(),v=qr(),w=qr();
rg fx=getfa(u),fy=getfa(v); //查找根
if(op==1){
if(fx!=fy){ fa[fx]=fy; //合并
d[fx]=((ll)d[u]+d[v]+w)%m; //一个联通块只有一个根，所以另一个需要改距离
g[fy]=gcd(gcd(g[fx],g[fy]),2*w); //更新联通块的gcd
}else g[fx]=gcd(gcd(g[fx],((ll)d[u]+d[v]+w)%m),2*w); //新加了一个环，合并环的贡献
} else{ //请注意大小写！！！！！！
rg ans=0,b=qr()%g[fx],c=qr(); //读入
if(fx!=fy){puts("0"); continue;} //不连通意味着不能到达
rg A=b,B=g[fx],G=gcd(A,B),C=(ll)d[u]+d[v]-w+B; //列出同余方程的系数
// 同余方程： C + x*A = 0 (mod B) -> x*A + y*B = C (mod g[fx])
if(C%G){puts("0"); continue;} //方程无解，请参见扩欧的做法
rg x,y; A/=G; B/=G; C/=G; //请参见扩欧的解方程的步骤
exgcd(A,B,x,y); x=((ll)x*C%B+B)%B; //解出同余方程
if(x<c)ans=(c-1-x)/B+1; //注意我们找的是x的最小解，循环长度是模数B！ （同余方程性质）
printf("%d\n",ans); //输出答案
}
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,q;
int d[1000005]; //并查集里面节点到其联通块的根的距离
int g[1000005]; //当前联通块的gcd，如天天爱跑步
int fa[1000005]; //并查集
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline int gcd(int a,int b){
if(b==0)return a; return gcd(b,a%b);
}
inline int getfa(int x){
if(x==fa[x])return x;
rg to=getfa(fa[x]); //注意顺序，防止信息被覆盖
d[x]=(d[x]+d[fa[x]])%m; //更新当前节点到根的距离
return fa[x]=to; //最后再赋值
}
inline void exgcd(int a,int b,int &x,int &y){ //扩展欧几里得
if(b==0) x=1,y=0; //直接构造一组解
else exgcd(b,a%b,y,x),y-=a/b*x; //我们不需要求gcd，只要解方程就好
}
int main(){
n=qr(); m=qr(); q=qr();
for(rg i=1;i<=n;++i) fa[i]=i,g[i]=m;
for(rg i=1;i<=q;++i){
rg op=qr(),u=qr(),v=qr(),w=qr();
rg fx=getfa(u),fy=getfa(v); //查找根
if(op==1){
if(fx!=fy){ fa[fx]=fy; //合并
d[fx]=((ll)d[u]+d[v]+w)%m; //一个联通块只有一个根，所以另一个需要改距离
g[fy]=gcd(gcd(g[fx],g[fy]),2*w); //更新联通块的gcd
}else g[fx]=gcd(gcd(g[fx],((ll)d[u]+d[v]+w)%m),2*w); //新加了一个环，合并环的贡献
} else{ //请注意大小写！！！！！！
rg ans=0,b=qr()%g[fx],c=qr(); //读入
if(fx!=fy){puts("0"); continue;} //不连通意味着不能到达
rg A=b,B=g[fx],G=gcd(A,B),C=(ll)d[u]+d[v]-w+B; //列出同余方程的系数
// 同余方程： C + x*A = 0 (mod B) -> x*A + y*B = C (mod g[fx])
if(C%G){puts("0"); continue;} //方程无解，请参见扩欧的做法
rg x,y; A/=G; B/=G; C/=G; //请参见扩欧的解方程的步骤
exgcd(A,B,x,y); x=((ll)x*C%B+B)%B; //解出同余方程
if(x<c)ans=(c-1-x)/B+1; //注意我们找的是x的最小解，循环长度是模数B！ （同余方程性质）
printf("%d\n",ans); //输出答案
}
}
return 0;
}
