「LibreOJ NOI Round #1」失控的未来交通工具
前言
怎么扩欧解方程都能错啊【流汗】。
题目
LibreOJ
讲解
写完感觉讲得一点都不清楚啊...果然这就是我的数学水平吗...
首先我们发现路径不是简单路径，所以任意一条边在一条路径上都可以多走偶数次(来回走即可)。
先不考虑环，\(u\rightarrow v\) 的路径上的边只能走奇数次，其它边只能走偶数次，因为走出去就必须要走回来。
而环可以走奇数次。
用带权并查集维护一下路径长度，然后维护一下连通块可以走出的最小周期(上面提到的路径长度与 \(m\) 的最大公因数)，最后用扩欧解一下方程，求答案即可。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
int n,m;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int f[MAXN],g[MAXN],d[MAXN];
int findSet(int x){
if(x == f[x]) return x;
int fa = findSet(f[x]);
d[x] = (d[x] + d[f[x]]) % m;
return f[x] = fa;
}
int gcd(int x,int y){
if(!y) return x;
return gcd(y,x%y);
}
int exgcd(int a,int b,int &x,int &y){
if(!b) {x = 1,y = 0;return a;}
int ret = exgcd(b,a%b,y,x); y -= a/b*x;
return ret;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read();
for(int i = 1;i <= n;++ i) f[i] = i,g[i] = m;
for(int Q = Read(); Q ;-- Q){
int opt = Read(),u = Read(),v = Read(),w = Read();
if(opt == 1){
int U = findSet(u),V = findSet(v);
if(U == V) g[V] = gcd(g[V],(0ll+d[u]+d[v]+w)%m);
else{
f[U] = V; d[U] = (0ll+d[u]+d[v]+w) % m;
g[V] = gcd(g[V],g[U]);
}
g[V] = gcd(g[V],w<<1);
}
else{
int b = Read(),c = Read(),U = findSet(u),V = findSet(v),x,y;
if(U ^ V){Put(0,'\n');continue;}
int dd = exgcd(b%g[V],g[V],x,y),jia = g[V]/dd; w = d[u]+d[v]-w;
if(w % dd){Put(0,'\n');continue;}
x = (1ll*x*(w/dd)%jia+jia)%jia;
if(x < c) Put((c-1-x)/jia+1,'\n');
else Put(0,'\n');
}
}
return 0;
}
/*
w,w+b,...,w+(c-1)b
w+bx = d[u]+d[v] \mod{G}
bx-Gy = d[u]+d[v]-w
*/