SGU 106 在区间范围内的线性方程解个数

题意：求解方程ax+by+c=0，在区间x1->x2和y1->y2的解的个数。

看似简单，真心a的不容易啊！

开始跪于第8组数据，原因是没用long long !后来改了，跪于12组，超时，于是，换方法，求出x的解，对应到y

，然后算在y1,y2的解有几个（不要用枚举法,算有几个就行）。竟然又跪于第4组数据！！哎，弱爆了。

才发现，x对应过去的y，x递增，y未必也递增，也未必递减啊！！

做线方程总结:

先判断有无解，再约分后得 ax+by=c，用扩展欧几里得求得ax+by=1的一解，x=x*c,y=y*c，便是原方程一组解了，

每俩个相邻解x，相差|b|，同理，y差|a|,然后就是看题目要求了，见招拆招了，如想要到去某点附近的解，

可以 x=x-(x1-x)/abs(b)*abs(b);(可能左右)。

#include<iostream>

#include<cmath>

using namespace std;

long long gcd(long long  a,long long  b)

{

    return b==0?a:gcd(b,a%b);

}

void exgcd(long long a,long long  b,long long &x,long long  &y)

{

    if(b==0){x=1;y=0;}

    else

    {

        exgcd(b,a%b,y,x);y=y-x*(a/b);

    }

}

inline long long getabs(long long  a)

{

  return a<0?-a:a;

}

int main()

{

    long long a,b,c,x1,x2,y1,y2;

    cin>>a>>b>>c>>x1>>x2>>y1>>y2;

    long long x,y;

    c=-c;                                         //移项

    if(x1>x2||y1>y2){cout<<0<<endl;return 0;}    //排除无解的情况

    if(a==0&&b==0)                               //特殊情况讨论

    {

        long long ans=0;

        if(c==0)

        {

             ans=(x2-x1+1)*(y2-y1+1);          //此处任意组合都可以

        }

          cout<<ans<<endl;

          return 0;

    }

    if(a==0)

    {

        if(c%b!=0){cout<<0<<endl;return 0;}

        else

        {

            y=c/b;

            if(y>=y1&&y<=y2)

                cout<<x2-x1+1<<endl;

            else cout<<0<<endl;

            return 0;

        }

    }

    if(b==0)

    {

        if(c%a!=0){cout<<0<<endl;return 0;}

        else

        {

            x=c/a;

            if(x>=x1&&x<=x2)cout<<y2-y1+1<<endl;

            else cout<<0<<endl;

            return 0;

        }

    }

    long long g=getabs(gcd(a,b));

    if(c%g!=0){cout<<0<<endl;return 0;}

    a=a/g;b=b/g;c=c/g;                       //约去最大公约数

    exgcd(a,b,x,y);                         //求得一组解

    x=x*c;

    y=y*c;                                 //原方程一组解

    x=x-(x-x1)/getabs(b)*getabs(b);        //得与x1最近的一解x（x>=x1）

    while(x<x1)x+=getabs(b);

    if(x>x2){cout<<0<<endl;return 0;}

    long long xx=x+(x2-x)/getabs(b)*getabs(b);  //解x->xx（x>=x1,xx<=x2）

    y=(c-a*x)/b;                           //对应yy，y,注意，此处yy,y大小不知道！！

    long long yy=(c-a*xx)/b;

    long long ans=0;

   /*   while(x<=xx)                      //若用枚举解，超时

      {

           if(y>=y1&&y<=y2)ans++;

           x+=getabs(b);

          y=(c-a*x)/b;

      }*/

     if(yy>y){long long temp=y;y=yy;yy=temp;}   //大小决定一下

       if(yy<y1)                               //取在区间y1->y2之间的解。（y,yy为边界解）

       {

           yy=yy+(y1-yy)/getabs(a)*getabs(a);

           while(yy<y1)yy+=getabs(a);

       }

       if(y2<y)

       {

           y=y-(y-y2)/getabs(a)*getabs(a);

           while(y>y2)y-=getabs(a);

       }

     if(y>=yy)

         ans=(y-yy)/getabs(a)+1;

    cout<<ans<<endl;

}

巴特西

SGU 106 在区间范围内的线性方程解个数

最新文章

热门文章