The equation - SGU 106(扩展欧几里得)

题目大意:有一个二元一次方程,给出系数值和x与y的取值范围,求出来总共有多少对整数解。

分析:有以下几点情况。

1,系数a=0, b=0, 当c != 0的时候结果很明显是无解,当c=0的时候x,y可以为任意值,答案就是(x2-x1+1)*(y2-y1+1)

2,系数a=0, b!=0, 先判断y的唯一解是否是整数,并且在[y1,y2]范围内,如果在,答案就是x的个数,x2-x1+1,否则为0

3,系数b=0,  a!=0, 先判断x的唯一解是否是整数,并且在[x1,x2]范围内,如果在,答案就是y的个数,y2-y1+1,否则为0

4,上面的特殊情况考虑完毕,因为要求余,但是给的系数是有负数的,所以先把负数转换成正数,符号转变的时候其所对应的取值范围也应对应转变,求出来x0,y0后,再用给定的范围求出t的范围,取两者交叉范围就是答案,注意向上向下取整问题,而且x计算出来的t是递增的,y 计算出来的t是递减的,要做相应转变。

代码如下:

===========================================================================================================

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
typedef long long LL;
using namespace std; LL ExGcd(LL a, LL b, LL &x0, LL &y0)
{
if(b == )
{
x0 = , y0 = ;
return a;
} LL d = ExGcd(b, a%b, x0, y0); swap(x0, y0);
y0 = y0 - a/b*x0; return d;
} int main()
{
LL a, b, c, x1, x2, y1, y2, x0, y0, ans = ; cin >> a >> b >> c;
cin >> x1 >> x2 >> y1 >> y2; c = -c;
if(c < ){c=-c; a=-a, b=-b;}
if(a < ){a=-a; swap(x1, x2), x1=-x1, x2=-x2;}
if(b < ){b=-b; swap(y1, y2), y1=-y1, y2=-y2;} if(a == && b==)
{
if(c == )
cout<< (y2-y1+)*(x2-x1+) <<endl;
else
cout << "" <<endl;
return ;
} if(a == )
{
if(c % b == && c/b >= y1 && c/b <= y2)
cout << x2-x1+ <<endl;
else
cout << "" <<endl; return ;
}
if(b == )
{
if(c % a == && c/a >= x1 && c/a <= x2)
cout << y2-y1+ <<endl;
else
cout << "" <<endl;
return ;
} LL d = ExGcd(a, b, x0, y0); if(c % d == )
{
a /= d, b /= d, c/=d;
x0 *= c, y0 *= c; LL L = max( ceil(1.0*(x1-x0)/b), ceil(1.0*(y0-y2)/a) );
LL R = min( floor(1.0*(x2-x0)/b), floor(1.0*(y0-y1)/a) ); if(L <= R)
ans = R-L+;
} cout << ans <<endl; return ;
}
上一篇:mybatis添加记录时返回主键id


下一篇:Mybatis在insert操作时返回主键