loj#508. 「LibreOJ NOI Round #1」失控的未来交通工具
https://loj.ac/p/508
贼牛逼的题目。想了两天才想明白。网上大多数题解都讲得很烂啊。
对于部分分的情况，我相信是较为容易想到的。因此，我只会阐述正解的思考过程及一些证明。
首先，考虑路径这东西太泛了。能否将其特殊化、具体化。
先观察一些性质。
-
对于一个环，我们可以走若干圈，会回到出发点，但对答案是有贡献的。
那么，我们是可以走 \(m\) 圈来抵消这个环的贡献的。 -
既然如此。考虑一条无向边是可以看成两条方向相反的有向边构成的，因此可以看成一个环，也就是说，我们可以经过一条无向边，并去到其他地方，最终回到该无向边的起点，从而这条无向边只是一个桥梁的作用，并没有贡献。注意，这里因为环是绕完后回原点，因此若想该边无贡献，则一定最终是回到起点的。
-
考虑 u-v 的路径上的边，我们是一定要经过一次的。那么，这一部分必须会有贡献。
-
考虑环的贡献，显然我们可以通过引理 2 得到，一个环可以有任意系数的贡献，并且是独立于其他环或者路径的。
事已至此，是不是一定就是 u-v 的某条路径有一个贡献，再与环进行线性组合，便能得到所有路径了呢？
但问题是，要 u-v 的哪条路径？
如果不能确定的话，这个问题将非常不可做。因此，我们猜想，一定可以确定或者使用其中某一条路径而得到正确的答案。
考虑环的线性组合能表示出来的一定是 \(\gcd(m,a_1,a_2,a_3,...,a_t)\) 的倍数，其中 \(a\) 是环长序列，那么对于任何一条路径 \(L\)，它一定有个 \(2L\) 在 \(\gcd\) 中，若 uv 路径唯一，则路径确定。若不唯一，则可以看成两条路径 \(L_1,L_2\)，那么这两条路径一定可以构成一个环，即 \(L_1+L_2,2L_1,2L_2\) 都在 \(\gcd\) 中，然后你考虑两条路径无交的地方一定会构成环，然后你去设参数，看看能否通过走这三种长度，来实现路径的替换。你会发现是可以的。
因此，我们只要随便找一条路径即可，因为环的线性组合与这条路径结合总能生成另一条路径。
那么，现在路径是随便找的了。我们可以直接并查集大力维护。注意在合并两棵树时，加的边不一定是在树根，此时魔改一下距离即可。
那么，如何维护环长的 \(\gcd\) 呢？
考虑加入 \((x,y,w)\)，如果没形成环，那么会多一个 \(2w\)。
若形成环，则多一个 \(2w\)，以及原先其若干路径 \(L\) 会形成 \(L+w\) 的环。
但因为，\(\gcd(L_1+w,L_2+w)=\gcd(L2+w,L1-L2),\gcd(2L_1,L_1+L_2)=\gcd(L_1+L_2,L_1-L_2)\)，你会发现，\(L_1-L_2\) 实际上已经加入了。所以我们只需要加入 \(L_2+w\) 即可。
即随便找一条路径。这与前面我们使用并查集维护的功能是相符合的。
接下来便是 exgcd，注意有点细节。
比如 \(ax+by=c\)，先求 \(ax+by=\gcd(a,b)\)，得到 \(x,y\)，然后乘上 \(c/\gcd(a,b)\)，再去设参数得到单次增量。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(1e6+5);
vector<int>vec[N];
int n,m,q,fa[N],dis[N],d[N];
int gcd(int x,int y) {
return !y?x:gcd(y,x%y);
}
int fd(int x) {
return x==fa[x]?x:fd(fa[x]);
}
void Merge(int x,int y,int w) { //把 y 放到 x 上
int fx=fd(x),fy=fd(y);
int D=dis[y]+w+dis[x];
fa[fy]=fx; d[fx]=gcd(d[fx],d[fy]);
// if(vec[fy].size()>vec[fx].size()) vec[fy].swap(vec[fx]);
for(int qwq:vec[fy]) dis[qwq]+=D,vec[fx].pb(qwq);
vector<int>().swap(vec[fy]);
}
void merge(int x,int y,int w) {
int fx=fd(x),fy=fd(y);
if(vec[fx].size()>vec[fy].size()) Merge(x,y,w);
else Merge(y,x,w);
}
pair<int,int> exgcd(int a,int b) {
if(!b) {
return make_pair(1,0);
}
pair<int,int> qwq=exgcd(b,a%b);
return make_pair(qwq.second,qwq.first-(int)(a/b)*qwq.second);
}
int lcm(int a,int b) {
return a/gcd(a,b)*b;
}
//int sol(int a,int b,int c,int Lim) {
// int ans=0;
// for(int i=0;i<=Lim;i++) {
// int qwq=c-a*i;
// if(qwq%b==0) ++ans;
// } return ans;
//}
int sol(int a,int b,int c,int Lim) {
if(c%gcd(a,b)!=0) return 0;
// cout<<a<<" "<<b<<" :c "<<c<<'\n';
int g=gcd(a,b);
pair<int,int> qwq=exgcd(a,b);
int D=b/g;
int x=qwq.first;
x=x*c/g;
x=(x%D+D)%D;
if(x>Lim) return 0;
int ans=(Lim-x)/D+1;
// int ans=1;
return ans;
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;i++) d[i]=m,fa[i]=i,vec[i].pb(i);
while(q--) {
int op; cin>>op;
if(op==1) {
int u,v,w; cin>>u>>v>>w;
if(fd(u)==fd(v)) {
int f=fd(u),L=dis[u]+dis[v];
// cout<<"! "<<f<<" "<<dis[u]<<" "<<dis[v]<<" "<<L<<'\n';
d[f]=gcd(d[f],gcd(2*w,L+w));
} else {
merge(u,v,w);
d[fd(u)]=gcd(d[fd(u)],2*w);
}
} else {
int u,v,x,b,c; cin>>u>>v>>x>>b>>c;
if(fd(u)!=fd(v)) {
cout<<"0\n"; continue ;
}
int f=fd(u),L=dis[u]+dis[v],ans=0;
// for(int i=0;i<c;i++) {
// int qwq=x+i*b;
// qwq-=L;
// qwq=(qwq%m+m)%m;
// if(qwq%d[f]==0) ++ans;
// }
// int qwq=L-x;
if(b==0) {
int qwq=(x-L)%m; qwq=(qwq+m)%m;
if(qwq%d[f]==0) cout<<c<<'\n';
else cout<<"0\n";
continue ;
}
cout<<sol(b,d[f],L-x,c-1)<<'\n';
}
}
return 0;
}