给定 \(a,b,L,R\)，找到最小的 \(p\geq 0\)，使得 \(pa\bmod b\in[L,R]\)。
设 \(qb\leq pa<(q+1)b\)。
等价于找到最小的 \(q\geq 0\)，使得存在 \(qb\leq pa<(q+1)b\) 满足 \(pa\bmod b\in [L,R]\)，即存在 \(p\) 满足 \(pa-qb\in[L,R]\)。
设 \(b=ka+r\)，转化为找到最小的 \(q\geq 0\)，使得存在 \(p\) 满足 \((p-qk)a-qr\in [L,R]\)。
注意到 \(q\) 确定后，\(p\) 的取值能使得 \((p-qk)a-qr\) 取到模 \(a\) 同余于 \(-qr\) 的任何数，于是，我们只需存在 \(x\in [L,R]\) 使得 \(-qr\equiv x\pmod a\) 即可。
若存在 \(x\in [L,R]\) 使得 \(x\) 是 \(a\) 的倍数，则 \(q=0\)；否则，我们需找到最小的 \(q\geq 0\) 使得 \(qr\bmod a\in[-R\bmod a,-L\bmod a]\)。
这就递归到了子问题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod(int x,int b)
{
return (x%b+b)%b;
}
int calc(int a,int b,int L,int R)//find min p and exist x in [L,R] that pa = x (mod b)
{
if(R-L+1>=b) return 0;
L=mod(L,b),R=mod(R,b);
if(L>R) return 0;
int k=b/a,r=b-k*a;
int q=calc(r,a,-R,-L);
return (q*b+L+a-1)/a;
}
int solve(int a,int b,int V,int M)
{
int p=calc(a,b,M-a+1-V,b-1-V);
int q=(V+p*a)/b;
assert(V+p*a-q*b+a>M);
return p+q;
}
signed main()
{
int T; cin>>T;
while(T--)
{
int A,B,V,M;
cin>>A>>B>>V>>M;
if(A+B<=M+1)
{
printf("%lld\n",M+1);
continue;
}
printf("%lld\n",solve(A,B,V,M)+solve(A,B,M-V,M)+1);
}
return 0;
}