【NOIP2013模拟11.7A组】不等式(solve)

本文主要是介绍【NOIP2013模拟11.7A组】不等式(solve)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【NOIP2013模拟11.7A组】不等式(solve)

题目

【NOIP2013模拟11.7A组】不等式(solve)
(File IO): input:solve.in output:solve.out
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits

Description
小z热衷于数学。

今天数学课的内容是解不等式：L<=S * x<=R。小z心想这也太简单了，不禁陷入了深深的思考：假如已知L、R、S、M，满足L<=(S * x)mod M<=R的最小正整数x该怎么求呢？

Input
第一行包含一个整数T，表示数据组数，接下来是T行，每行为四个正整数M、S、L、R。

Output
对于每组数据，输出满足要求的x值，若不存在，输出-1。

Sample Input
1

5 4 2 3

Sample Output
2

Data Constraint
30%的数据中保证有解并且答案小于等于10^6；

另外20%的数据中保证L=R；

100%的数据中T<=100，M、S、L、R<=10^9。

题解

这是一道类欧的题目
根据拓展欧几里得的思路，我们将一个值的求法通过另一个范围更小，更容易求的题目的答案来得到。有一点像数学归纳法。
复习一下拓欧：求解ax+by=gcd(a,b)的不定方程。可以通过gcd(a,b)=gcd(b,a%b)将范围缩小。再通过转换，使得x、y适用于大范围的方程。
同理，我们这道题也可以这么做。
Step1 将(s * x)%m 转换成s * x-m * p.
于是，变成求解l<=s * x-m * p<=r.
Step2 将主元换成p
-r<=m * p-s * x<=-l
我们发现，x的取值应该是使得s * x刚刚好小于0的那个数。所以，我们推论：m * p-s * x>-p.
所以，m * p-s * x=m*p%s
两边同时取模。
-r%s<=m * p%s<=-l%s
(-r%s+s)%s<=(m * p)%s<=(-l%s+s)%s.
这样，我们就可以像拓欧那样求解不定不等式方程。
但是，为什么这样会使范围缩小呢？
（-l%s+s)%s-(-r%s+s)%s.
原式=(-l%s+s-(-r%s+s))%s=(-l%s+s-s+r%s)%s=(r-l)%s.
因为(r-l)%s<=(r-l) 范围不停变小。

什么时候范围合适呢？
当可以满足l<=s*x<=r有解时。且x一定是最小解。

范围处理有一些复杂

代码

#include<cstdio>
using namespace std;
int t,m1,s1,l1,r1;
long long gcd(long long m,long long s,long long l,long long r)
{if (r>=m) r=m-1;s=s%m;if (l>r||l>=m) return -1;if (l==0) return 0;if (((l-1)/s+1)*s<=r) return (((l-1)/s+1));long long exgcd=gcd(s,m,((-r%s+s)%s),((-l%s+s)%s));if (exgcd==-1) return -1;long long y=exgcd;long long ans=(l+m*y-1)/s+1;if (s*ans-m*y<=0) return -1;else	return ans;
}
int main()
{freopen("solve.in","r",stdin);freopen("solve.out","w",stdout);scanf("%d",&t);for (int times=1;times<=t;times++){scanf("%d%d%d%d",&m1,&s1,&l1,&r1);printf("%lld\n",gcd(m1,s1,l1,r1));}
}