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; }