1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
| #include<bits/stdc++.h> using namespace std;
typedef long long ll;
typedef pair<int , int > pii; typedef unsigned long long ull;
namespace FastIO { template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } }; using namespace FastIO;
ll A, B, C, lx, rx, ly, ry;
inline void Input() { read(A, B, C, lx, rx, ly, ry); }
inline void Exgcd(ll a, ll b, ll&x, ll&y) { if(b == 0) x = 1, y = 0; else Exgcd(b, a % b, y, x), y -= (a / b) * x; }
inline void Work() { C = -C; if(A == 0 && B == 0) { if(C == 0) printf("%lld\n", (rx - lx + 1) * (ry - ly + 1)); else printf("0\n"); return ; } else if(A == 0) { if(C % B) printf("0\n"); else if(C / B < ly || C / B > ry) printf("0\n"); else printf("%lld\n", rx - lx + 1); return ; } else if(B == 0) { if(C % A) printf("0\n"); else if(C / A < lx || C / A > rx) printf("0\n"); else printf("%lld\n", ry - ly + 1); return ; } int g = __gcd(A, B); if(C % g) { printf("0\n"); return ; } ll x, y; Exgcd(A, B, x, y); x = x * (C / g), y = y * (C / g); ll xx = B / g, yy = A / g; lx = ((x - lx) % xx + abs(xx)) % abs(xx) + lx; rx = ((x - rx) % xx - abs(xx)) % abs(xx) + rx; if(lx > rx) { printf("0\n"); return ; } ll Ymn = (-yy) * ((lx - x) / xx) + y; ll Ymx = (-yy) * ((rx - x) / xx) + y; if(Ymn > Ymx) swap(Ymn, Ymx); ly = max(ly, Ymn), ry = min(ry, Ymx); ly = ((y - ly) % yy + abs(yy)) % abs(yy) + ly; ry = ((y - ry) % yy - abs(yy)) % abs(yy) + ry; if(ly > ry) { printf("0\n"); return ; } printf("%lld\n", (ry - ly) / abs(yy) + 1); }
int main() { int T = read(), ca = 0; while(T--) { Input(); printf("Case %d: ", ++ca); Work(); } return 0; }
|