当前位置: 代码迷 >> 综合 >> The equation(exgcd+解不等式方程组)
  详细解决方案

The equation(exgcd+解不等式方程组)

热度:28   发布时间:2023-11-27 04:17:31.0

The equation

推荐博客:http://www.cnblogs.com/Rinyo/archive/2012/11/25/2787419.html


There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the following conditions : x1<=x<=x2,   y1<=y<=y2. Integer root of this equation is a pair of integer numbers (x,y).

Input

Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks. All numbers are not greater than 108 by absolute value.

Output

Write answer to the output.

Sample Input

1 1 -3
0 4
0 4

Sample Output

4


 
#include <bits/stdc++.h>using namespace std;typedef long long ll;ll exgcd(ll a,ll b,ll &x,ll &y)
{if (b==0){x=1;y=0;return a;}ll d =exgcd(b,a%b,x,y);ll t=x ;x=y;y=t-a/b*y;return d;
}//exgcd 板子题,不过后台数据还是可以的,
/*****
特殊情况的三种判断,a==0,b==0;a==0,b!=0,a==0,b!=0;
第四种情况,exgcd,
本身自己大算在第四中情况中先找到x的范围,在对应的跑完对应y的范围,结果第十二组测试数据卡超时
只好找x的范围,y的范围,求其交集,即为最后的答案。。
自己wa进30发。。。。:(
最后想说的是,学会了两个函数,
floor(),向下取整,
ceil()向上取整,
举例
[2.5,4.5]对应的范围应该是[3,4],
[-3.5,5.5]对应的范围应该是[-3,5];
所以上去下界,下去上届。****/
int main ()
{ll a,b,c,l_x,r_x,xx,xxx,x,y,yy,yyy;cin>>a>>b>>c>>xx>>xxx>>yy>>yyy;ll ans=0;c=-c;if (a==0&&b==0){if (c==0)//最 zz的一次,竟然不加这个判断,不加的话,等式不成立。。。。。ans =(xxx-xx+1)*(yyy-yy+1);}else if (a==0&&b!=0){if (c%b==0 && (c/b)>=yy && (c/b)<=yyy)ans=(xxx-xx+1);}else if (a!=0&&b==0){if (c%a==0&&(c/a)>=xx&&(c/a)<=xxx)ans=(yyy-yy+1);}else{ll d=exgcd(a,b,x,y);double  aa,bb;if (c%d==0){x=c/d*x;y=c/d*y;aa=-(a/d);bb=b/d;if(bb>0){l_x=ceil(((double)xx-x)/bb);r_x=floor(((double)xxx-x)/bb);}else{l_x=ceil(((double)xxx-x)/bb);r_x=floor(((double)xx-x)/bb);}ll l_y,r_y;if(aa>0){l_y=ceil(((double)yy-y)/aa);r_y=floor(((double)yyy-y)/aa);}else{l_y=ceil(((double)yyy-y)/aa);r_y=floor(((double)yy-y)/aa);}ans =min(r_x,r_y)-max(l_x,l_y)+1;if(ans<0)ans=0;}}cout<<ans<<endl;return 0;
}


  相关解决方案