Solutions to an Equation LightOJ

一个基础的扩展欧几里得算法的应用。

解方程ax+by=c时，基本就是先记录下a和b的符号fla和flb（a为正则fla为1，为负则fla为-1，flb相同），然后对a和b取绝对值。求出ax+by=gcd(a,b)的一组解x=ansx,y=ansy，那么只有当c是gcd(a,b)的倍数时原方程才可能有解。设g=gcd(a,b)，通解是x=ansx*(c/g)*fla+k*b/g*fla,y=ansy*(c/g)*flb-k*a/g*flb。这里设xa=ansx*(c/g)*fla，xb=b/g*fla，ya=ansy*(c/g)*flb，yb=-(a/g*flb)。

那么这题就是根据通解的式子和x和y的范围去求k的范围，基本操作就是手算一下解不等式。

举例：不等式(x相关)：xa+k*xb>=x1,xa+k*xb<=x2

（解一下就会发现第一个式子解出的是k的最小值还是最大值，与xb的符号有关）

理论上不难，但是符号之类的细节实现起来有难度（...）。另外，a为0或b为0或a、b都为0时都需要特判（...）。

错误记录：

未特判0

upd:

以上应该有错。通解应该是x=ansx*fla+k*(b/g)*fla,y=ansy*flb-k*(a/g)*flb

通解就是那个没错的，但是要注意ansx和ansy是ax+by=gcd(a,b)的解，不是原方程的解。

如果有了一组原方程的解，求通解，那么就不要乘c/g

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<algorithm>
  4 using namespace std;
  5 typedef long long LL;
  6 LL T,x,y,a,b,c,x1,x2,y11,y2,g;
  7 LL gcd(LL a,LL b)
  8 {
  9     LL t;
 10     while(b!=0)
 11     {
 12         t=a;
 13         a=b;
 14         b=t%b;
 15     }
 16     return a;
 17 }
 18 LL exgcd(LL a,LL b,LL& x,LL& y)
 19 {
 20     if(b==0)
 21     {
 22         x=1;
 23         y=0;
 24         return a;
 25     }
 26     else
 27     {
 28         LL t=exgcd(b,a%b,x,y);
 29         LL t1=x;
 30         x=y;
 31         y=t1-a/b*y;
 32         return t;
 33     }
 34 }
 35 int main()
 36 {
 37     LL TT,fla,flb,xa,xb,ya,yb,kl,kr,kl1,kr1;
 38     scanf("%lld",&T);
 39     for(TT=1;TT<=T;TT++)
 40     {
 41         scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x1,&x2,&y11,&y2);
 42         c=-c;
 43         if(a==0&&b==0)
 44         {
 45             if(c==0)
 46             {
 47                 printf("Case %lld: %lld
",TT,max(0ll,(x2-x1+1)*(y2-y11+1)));
 48             }
 49             else
 50             {
 51                 printf("Case %lld: %lld
",TT,0ll);
 52             }
 53             continue;
 54         }
 55         if(a==0)
 56         {
 57             if(c%b==0&&(c/b>=y11)&&(c/b<=y2))
 58                 printf("Case %lld: %lld
",TT,x2-x1+1);
 59             else
 60                 printf("Case %lld: %lld
",TT,0ll);
 61             continue;
 62         }
 63         if(b==0)
 64         {
 65             if(c%a==0&&(c/a>=x1)&&(c/a<=x2))
 66                 printf("Case %lld: %lld
",TT,y2-y11+1);
 67             else
 68                 printf("Case %lld: %lld
",TT,0ll);
 69             continue;
 70         }
 71         fla=1;flb=1;
 72         if(a<0)
 73         {
 74             a=-a;
 75             fla=-1;
 76         }
 77         if(b<0)
 78         {
 79             b=-b;
 80             flb=-1;
 81         }
 82         g=gcd(a,b);
 83         if(c%g!=0)
 84         {
 85             printf("Case %lld: %lld
",TT,0ll);
 86             continue;
 87         }
 88         exgcd(a,b,x,y);
 89         xa=x*(c/g)*fla;
 90         xb=b/g*fla;
 91         ya=y*(c/g)*flb;
 92         yb=-(a/g*flb);
 93         //x=xa+k*xb,y=ya+k*yb
 94         if(xb>0)
 95         {
 96             kl=ceil((double)(x1-xa)/xb);
 97             kr=floor((double)(x2-xa)/xb);
 98         }
 99         else
100         {
101             kr=floor((double)(x1-xa)/xb);
102             kl=ceil((double)(x2-xa)/xb);
103         }
104         if(yb>0)
105         {
106             kl1=ceil((double)(y11-ya)/yb);
107             kr1=floor((double)(y2-ya)/yb);
108         }
109         else
110         {
111             kr1=floor((double)(y11-ya)/yb);
112             kl1=ceil((double)(y2-ya)/yb);
113         }
114         //if(kl1>kr1)    swap(kl1,kr1);
115         printf("Case %lld: %lld
",TT,max(min(kr1,kr)-max(kl1,kl)+1,0ll));
116     }
117     return 0;
118 }