原題：
http://172.16.0.132/senior/#contest/show/2061/2
題目描述：
小z熱衷于數(shù)學(xué)怠李。
今天數(shù)學(xué)課的內(nèi)容是解不等式：L<=Sx<=R捺癞。小z心想這也太簡(jiǎn)單了髓介，不禁陷入了深深的思考：假如已知L箱歧、R叫胁、S微谓、M仲智，滿足L<=(Sx)mod M<=R的最小正整數(shù)x該怎么求呢钓辆？
輸入：
第一行包含一個(gè)整數(shù)T功戚，表示數(shù)據(jù)組數(shù)，接下來(lái)是T行乘粒，每行為四個(gè)正整數(shù)M、S、L他爸、R。
輸出：
對(duì)于每組數(shù)據(jù)讨跟，輸出滿足要求的x值，若不存在，輸出-1澜共。
樣例輸入：
1
5 4 2 3
樣例輸出：
2
數(shù)據(jù)范圍限制：
30%的數(shù)據(jù)中保證有解并且答案小于等于10^6瘦黑；
另外20%的數(shù)據(jù)中保證L=R；
100%的數(shù)據(jù)中T<=100，M冗栗、S葛虐、L涕蚤、R<=10^9西疤。
分析：
對(duì)于的做法扰她，首先我們排除特殊情況芭碍，不妨設(shè),0<=l<=r,0<=s<=m徒役。
顯然若存在一個(gè)的倍數(shù)滿足l<=sx<=r，那么此時(shí)的答案就是x窖壕。
若不存在忧勿，我們不妨將約束式改寫成代數(shù)式l<=sx-my<=r。進(jìn)一步改寫成以為y主元瞻讽，即-r<=my-sx<=-l狐蜕，再把它還原為取模的形式：(-r mod s)<=my mod s<=(-l mod s)。若能求出最小的滿足上式的y值卸夕，則可以求出唯一滿足上式的x值（因?yàn)閰^(qū)間中沒有s的倍數(shù)）。
所以我們只需要將讀入的四個(gè)數(shù)標(biāo)準(zhǔn)化婆瓜，判斷是否存在簡(jiǎn)單解以及判斷無(wú)解快集，假如需要的話遞歸調(diào)用函數(shù)贡羔，直至問題解決。
實(shí)現(xiàn)：
#include<cstdio>
long long t,m,s,l,r;
long long dg(long long m,long long s,long long l,long long r)
{
if(l==0) return 0;
if(l>=m || l>r || s%m==0) return -1;
s%=m;
long long x=(l-1)/s+1;
if(x*s<=r) return x;
long long y=dg(s,m,(-r%s+s)%s,(-l%s+s)%s);
if(y==-1) return y;
x=(r+m*y)/s;
if(s*x-m*y>=l) return (x%m+m)%m;
return -1;
}
int main()
{
freopen("solve.in","r",stdin);freopen("solve.out","w",stdout);
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld%lld",&m,&s,&l,&r);
if(r>=m) r=m-1;
printf("%lld\n",dg(m,s,l,r));
}
}
