EXGCD - The equation - SGU 106

EXGCD - The equation - SGU 106

题意：

$给定整数：a,b,c,l_1,r_1,l_2,r_2，对方程ax+by+c=0，计算有多少组整数解(x_0,y_0)，$

$满足：l_1\le x_0\le r_1\ 且\ l_r\le y_0\le r_2。$

输入：

$整数a,b,c,l_1,r_1,l_2,r_2，所有整数的绝对值均不超过10^8。$

输出：

$一个整数表示答案。$

Sample Input

1 1 -3
0 4
0 4

Sample Output

4

分析：

$解ax+by+c=0，用扩展欧几里得算法，记d=gcd(a,b)，$

$先解方程ax+by=d，假设方程有解，且a>0,b>0，(x_0,y_0)是一组特殊解，$

$则方程通解的形式为：\begin{cases}x=x_0+kb'\\y=y_0-ka'\end{cases}，其中b'=\frac{b}{d}，a=\frac{a}{d}.$

$然后我们将x和y同时扩大$ $\frac{-c}{d}$ $倍。$

$要求解(x,y)满足：\begin{cases}l_1\le x\le r_1\\l_2\le y\le r_2\end{cases}，即$ $\begin{cases}\frac{l_1-x_0}{b'}\le k\le\frac{r_1-x_0}{b'}\\\\\frac{y_0-r_2}{a'}\le k\le \frac{y_0-l_2}{a'}\end{cases}$

$然后我们取区间的交集，就能够计算出满足条件的k的个数，即整数解对的个数。$

$当a<0时，我们可以计算(-a)x+by=-c，且满足l_1\le -x\le r_1，l_2\le y\le r_2的整数解对(x,y)的数量。$

$当b<0时，同理。$

$当-c<0时，在方程两边同时乘-1，即将a变为-a，b变为-b，就能够不更改解所在的区间。$

$这样我们能够减少分类讨论的情况。$

特殊情况：

$①、a=b=0，$

$\qquadⅠ、c=0，此时任意的(x,y)均满足条件，答案：(r_1-l_1+1)×(r_2-l_2+1)$

$\qquad Ⅱ、c≠0，无解。$

$②、a=0，b≠0，解by=-c，先判断-\frac{c}{b}是否在区间[l_2,r_2]内，若在，答案为r_1-l_1+1；否则为0.$

$③、a≠0，b=0，同理。$

注意：

$区间左端点处应当为上取整，右端点应当为下取整。$

$x和y的范围在10^8，在扩展欧几里得计算的过程中可能会爆int，故x,y要开ll，尤其要注意有乘法的部分。$

$由于区间端点可能有负数，故向上取整和和向下取整时最好用ceil和floor函数来完成。$

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>#define ll long longusing namespace std;int exgcd(int a,int b,ll &x,ll &y)
{if(b==0){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;
}int main()
{int a,b,c,l1,r1,l2,r2;ll x,y;ll ans;cin>>a>>b>>c>>l1>>r1>>l2>>r2;if(a==0&&b==0){if(c!=0) ans=0;else ans=(ll)(r1-l1+1)*(r2-l2+1);}else if(a==0&&b!=0){if(abs(c)%b!=0) ans=0;else{int t=-c/b;if(t>=l2&&t<=r2) ans=r1-l1+1;else ans=0;}}else if(a!=0&&b==0){if(abs(c)%a!=0) ans=0;else {int t=-c/a;if(t>=l1&&t<=r1) ans=r2-l2+1;else ans=0;}} else{if(c>0) c=-c, a=-a, b=-b;if(a<0) a=-a, l1=-l1, r1=-r1, swap(l1,r1);if(b<0) b=-b, l2=-l2, r2=-r2, swap(l2,r2);int d=exgcd(a,b,x,y);if(abs(c)%d!=0) ans=0;else{int b1=b/d, a1=a/d;x=x/d*(-c), y=y/d*(-c);int L1=ceil((double)(l1-x)/b1), R1=floor((double)(r1-x)/b1);int L2=ceil((double)(y-r2)/a1), R2=floor((double)(y-l2)/a1);int L=max(L1,L2), R=min(R1,R2);ans=max(0,R-L+1);}}cout<<ans<<endl;return 0;
}