math - Solution of linear diaphantine equation.

// Number of solutions of a diaphantine equation. in a range
// Tested - LOJ 1306
#include <bits/stdc++.h>
using namespace std;
typedef long long i64d;

i64d x, y, d;

void extEuclid(i64d a, i64d b) {
   if (b == 0) { x = 1; y = 0; d = a; return; }
   extEuclid(b, a % b);
   x = x - (a / b) * y;
   swap(x, y);
}
// solution of ax+by=c, where x1<=x<=x2, y1<=y<=y2
i64d solve(i64d a,i64d b,i64d c,i64d x1,i64d x2,i64d y1,i64d y2)
{

   if(a==0&&b==0){
      if(c==0) return (x2-x1+1)*(y2-y1+1);
      return 0;
   }
   if(a==0){
      if(c%b==0 && y1 <= c/b &&  c/b <= y2)  return (x2-x1+1);
      return 0;
   }
   if(b==0) {
      if(c%a==0 && x1 <= c/a && c/a <= x2) return (y2-y1+1);
      return 0;
   }
   extEuclid(a,b);
   if(c%d==0) {
      x *= c/d, y *= c/d;
      b /= d , a /= d;
      swap(a,b);
      double p = (x1-x)/(double) a , q = (x2-x)/(double) a;
      if(p>q) swap(p,q);
      x1 = (i64d) ceil(p), x2 = (i64d ) floor(q);

      p = (y - y1)/(double)b, q  = (y - y2) / (double)b ;
      if(p>q) swap(p,q);
      y1 = (i64d) ceil(p) , y2 = (i64d) floor(q);

      x1 = max(x1,y1), x2 = min(x2,y2);
      return max(0LL , x2-x1+1);
   }
   return 0;
}

int main()
{
   int t,cs=0,a,b,c,x1,y1,x2,y2;
   scanf("%d",&t);
   while(t--) {
      scanf("%d %d %d %d %d %d %d",&a,&b,&c,&x1,&x2,&y1,&y2);
      printf("Case %d: %lld\n",++cs, solve(a,b,-c,x1,x2,y1,y2));
   }
}