LightOJ 1306Solutions to an Equation

LightOJ 1306 Solutions to an Equation

You have to find the number of solutions of the following equation:

Ax + By + C = 0

Where A, B, C, x, y are integers and x₁ ≤ x ≤ x₂ andy₁ ≤ y ≤ y₂.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing seven integers A, B, C, x₁, x₂, y₁, y₂ (x₁ ≤ x₂, y₁ ≤ y₂). The value of each integer will lie in the range [-10⁸, 10⁸].

Output

For each case, print the case number and the total number of solutions.

Sample Input

5

1 1 -5 -5 10 2 4

-10 -8 80 -100 100 -90 90

2 3 -4 1 7 0 8

-2 -3 6 -2 5 -10 5

1 8 -32 0 0 1 10

Sample Output

Case 1: 3

Case 2: 37

Case 3: 1

Case 4: 2

Case 5: 1

  题意：     给你一个方程求有多少组解。  给定的数正负零都可以。

  巨怕这种题（orz）

 

  思路： 扩欧的应用，注意正负零的特判，还有   其他的一些情况

#pragma comment(linker, "/STACK:1024000000,1024000000") //#include <bits/stdc++.h> #include<string> #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<queue> #include<stack> #include<vector> #include<algorithm> #define maxn 10010 #define INF 0x3f3f3f3f #define eps 1e-8 #define MOD 1000000007 #define ll long long using namespace std; ll exgcd(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= (a / b)*x; return d; } int main() { int T; int cnt = 0; cin >> T; while(T--) { ll a, b, c, x1, x2, y1, y2; scanf("%lld%lld%lld", &a, &b, &c); scanf("%lld%lld%lld%lld",&x1, &x2, &y1, &y2); c = -c; if(a < 0) { a = -a; swap(x1, x2); x1 = -x1; x2 = -x2; } if(b < 0) { b = -b; swap(y1, y2); y1 = -y1; y2 = -y2; } printf("Case %d: ", ++cnt); ll x0 = 0 , y0 = 0; ll g = exgcd(a, b, x0, y0); if(g!=0 && c % g != 0) { printf("0\n"); continue; } if(a == 0 && b == 0) { if(!c) printf("%lld\n", (x2 - x1 + 1) * (y2 - y1 + 1)); else printf("0\n"); continue; } if(a == 0) { if(c / b >= y1 && c / b <= y2) printf("%lld\n", x2 - x1 + 1); else printf("0\n"); continue; } if(b == 0) { if(c / a >= x1 && c / a <= x2) printf("%lld\n", y2 - y1 + 1); else printf("0\n"); continue; } x0 = x0 * c / g; y0 = y0 * c / g; a /= g; b /= g; ll l = ceil((double)(x1 - x0)/(double)(b)); ll r = floor((double)(x2 - x0)/(double)(b)); ll w = ceil((double)(y0 - y2)/(double)(a)); ll e = floor((double)(y0 - y1)/(double)(a)); ll q = max(l, w); ll p = min(r, e); if(p < q) printf("0\n"); else printf("%lld\n", p - q + 1); } return 0; } //向上取整（ceil()） 向下取整（floor）