她
【问题描述】
给你L,R,S,M，求满足L≤ (S × x) mod M ≤ R最小的正整数 X。
【输入格式】
第一行一个数T代表数据组数。
接下来一行每行四个数代表该组数据的L,R,S,M。
【输出格式】
对于每组数据，输出一行代表答案。如果不存在解，输出“−1” 。
【样例输入】
1
5 4 2 3
【样例输出】
2
【样例解释】
叫南小鸟。
【数据规模与约定】
30%的数据，保证有解且答案不超过10^ 6 。
另外20%的数据，L = R。
对于100%的数据，1 ≤ T ≤ 100,0 ≤ M,S,L,R ≤ 10 ^9
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+;
int a[N],top;
int erfen(int x){
int l=,r=top,mid,res=;
while(l<=r){
mid=(l+r)>>;
if(a[mid]>=x) res=mid,r=mid-;
else l=mid+;
}
return res;
}
int main(){
freopen("she.in","r",stdin);
freopen("she.out","w",stdout);
int i,j,k,n,m,s,l,r,x,now,t,ans,ans2;
bool fl;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&m,&s,&l,&r);
if(l>=m){printf("-1\n");continue;}
if(r>=m)r=m-;
now=;fl=;
top=;
for(n=;n*n<=m;n++){
now=(now+s)%m;
if(l<=now&&now<=r){
printf("%d\n",n);
fl=;break;
}
a[++top]=now;
}
--n;
int ste=a[top];
if(fl) continue;
sort(a+,a+top+);
for(now=;now*n<=m;now++){
l=(l-ste+m)%m;r=(r-ste+m)%m;
if(l>r) {
if(a[top]>=l){fl=;break;}
if(a[]<=r){fl=;break;}
}
else{
if(a[top]<l) continue;
int x=erfen(l);
if(a[x]<=r){fl=;break;}
}
}
if(!fl){printf("-1\n");continue;}
ans=now*n;
now=;
for(i=;i<=top;i++){
now=(now+s)%m;
if(l<=now&&now<=r)break;
}
ans+=i;
printf("%d\n",ans);
}
return ;
}