（为了方便，以下除$V$外都改为小写字母）
结论1：若$a+ble m+1$，则答案为$m+1$（即任意$x$都可以被得到）
任取$yin [0,m]$，由$gcd(a,b)=1$存在$y-V=pa+qb$，且不妨假设$pin [0,b)$
不断对$x+a$直至加了$p$次或无法再加，对两种情况分别处理：
1.若为前者，此时再通过若干次$pm b$一定可以得到$y$
2.若为后者，由$a+ble m-1$一定可以将$x-b$，进而重复此过程即可
注意到$-b$后一定可以$+a$（$a<b$），因此该过程有限，即可以得到$y$
特判此情况后，即有$a+bge m+2$
考虑某次$+a$操作后，其不能$-a$（显然无意义）或$+b$（根据$a+bge m+2$），那么只能$+a$或$-b$，而同样根据$a+bge m+2$，这两个操作中至多只有一个可以执行
类似地分析其余操作，实际上只有两种方案：
1.每一次使用$+a$和$-b$中可以执行的一种操作
2.每一次使用$-a$和$+b$中可以执行的一种操作
注意到是操作是确定的，因此可以看作两条从$V$开始的链
结论2：这两条链上除了$V$以外无公共点
先来证明一条链内部无公共点，不妨以第一条链为例：
注意到每一个点之后的状态是确定的，因此重复即出现循环，同时最小的循环节中不会出现重复的数
任取循环中的某个点$x$，假设其到下一次$x$一共执行了$p$次$+a$和$q$次$-b$，即有$pa=qb$
而$gcd(a,b)=1$，因此有$amid q$且$bmid p$，同时$p,qin Z^{+}$，不难得到$p+qge a+bge m+2$，根据抽屉原理必然存在重复的数，矛盾
再来证明两条链中无公共点（除$V$以外），注意到前者总可以沿着后者的逆过程回到$V$，同时根据唯一性这必然就是该链本身，即重复经过$V$（注意一条链内也不允许重复经过$V$），与之前所述矛盾
综上，即得证
由此，答案即两链链长（指边数）和+1，根据对称性不妨仅考虑第一条链：
不妨考虑该链中$+a$的次数（假设有$p$次，不难推出链长为$p+lfloorfrac{V+pa}{b} floor$），此时$-b$即可以直接对$b$取模，因此即求最小的$p$使得$(V+pa)mod b+a>m$
令$V_{0}=V mod b$，特判$V_{0}+a>m$的情况，此时显然$p=0$
若$V_{0}+ale m$，必然要有$V_{0}+pa mod b<b$，进而原式即为$V_{0}+pa mod b+a<m$
换言之，原式等价于$pa mod bin [L,R]$（其中$L=m-a-V_{0}+1$且$r=b-V_{0}-1$）
不妨假设$b=ka+r$（其中$0le r<a$）且$qble pa<(q+1)b$，那么限制即
$$
pa-qb=(p-qk)a-qrin [L,R]Longrightarrow qr mod ain [L',R']
$$
（其中$L'$和$R'$即$(-R)mod a$和$(-L)mod a$，且若其包含0直接取$q=0$即可）
得到满足此条件最小的$q$后（递归），不难解得$p=lceilfrac{qb+L}{a} ceil$，且显然其也为最小
过程即为辗转相除，时间复杂度为$o(tlog m)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int t,a,b,V,m; 5 int get(int a,int b,int L,int R){ 6 if (!a)return 0; 7 int q=0; 8 if ((L-1)/a==R/a)q=get(b%a,a,(a-R%a)%a,(a-L%a)%a); 9 return ((ll)q*b+L+a-1)/a; 10 } 11 int calc(int a,int b,int V,int m){ 12 int V0=V%b,p=0; 13 if (V0+a<=m)p=get(a,b,m-a-V0+1,b-V0-1); 14 return p+(V+(ll)p*a)/b; 15 } 16 int main(){ 17 scanf("%d",&t); 18 while (t--){ 19 scanf("%d%d%d%d",&a,&b,&V,&m); 20 if (a+b<=m+1)printf("%d ",m+1); 21 else printf("%d ",calc(a,b,V,m)+calc(b,a,V,m)+1); 22 } 23 return 0; 24 }