SGU 106 The equation(拡張ユークリッド)

Description求める方程式ax+by+c=0のx 1<=x 2かつy 1<=y 2の解を満たす個数Input 7個の整数a,b,c,x 1,x 2,y 1,y 2,すべての数の絶対値が10^8 Output出力解の個数Sample Input 1-3 0 4 0 4 Sample Output 4 Solutionの特殊な場合の処理詳細はコードを参照してください.ここでa,b>0,gcd(a,b)=1が拡張ユークリッドからax+by=1を満たす(x,y)の組を得ることができ、x=cx,y=cyにax+by=cを満たす解(x,y)の組を得ることができる.(x+tb,y-ta)も方程式の解であり、各tはx 1<=x+tb<=x 2およびy 1<=y-ta<=x 2およびy 1<=y-ta<=y 2から得られたtの取値範囲が(l,r)のl=max((x 1-x)/b,(y-y 2)/a)であり、r=r=r=r=r=r=r=max(=y-y 2)/a)min((x 2-x)/b、(y-y 1)/a)では解の個数はmax(r-l+1,0)Codeである

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
    if(!b)return a;
    return gcd(b,a%b);
}
ll extend_gcd(ll a,ll b,ll &x,ll &y)
{ 
    ll d=a;
    if(b!=0) d=extend_gcd(b,a%b,y,x),y-=(a/b)*x;
    else x=1,y=0;
    return d;
}
int main()
{
    ll a,b,c,x1,y1,x2,y2;
    while(~scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x1,&x2,&y1,&y2))
    {
        ll ans;
        c=-c;
        if(c<0)c=-c,a=-a,b=-b;
        if(a<0)a=-a,swap(x1,x2),x1=-x1,x2=-x2;
        if(b<0)b=-b,swap(y1,y2),y1=-y1,y2=-y2;
        if(x1>x2||y1>y2)ans=0;
        else if(a==0&&b==0)
        {
            if(c==0)ans=1ll*(x2-x1+1)*(y2-y1+1);
            else ans=0;
        }
        else if(a==0)
        {
            if(c%b==0&&c/b>=y1&&c/b<=y2)ans=x2-x1+1;
            else ans=0;
        }
        else if(b==0)
        {
            if(c%a==0&&c/a>=x1&&c/a<=x2)ans=y2-y1+1;
            else ans=0;
        }
        else
        {
            ll g=gcd(a,b);
            if(c%g!=0)ans=0;
            else
            {
                a/=g,b/=g,c/=g;
                ll x,y;
                extend_gcd(a,b,x,y);
                x*=c,y*=c;
                ll l1=ceil(1.0*(x1-x)/b),l2=ceil(1.0*(y-y2)/a);
                ll r1=floor(1.0*(x2-x)/b),r2=floor(1.0*(y-y1)/a);
                ll r=min(r1,r2),l=max(l1,l2);
                ans=l<=r?r-l+1:0;
            }
        }
        printf("%lld
",ans);
    }
}