2009年11月25日星期三.sgu106
這題終于過了......
太容易錯了
忘了sgu是ms win,用%lld錯了十幾次，干脆cin就得了,I64d在linux又編譯不了
106. The equation
There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how
many integer roots of this equation are satisfy to the following conditions :
x1<=x<=x2, y1<=y<=y2. Integer root of this equation is a pair of integer numbers
(x,y).
Input
Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks.
All numbers are not greater than 108 by absolute value.
Output
Write answer to the output.
Sample Input
1 1 -3
0 4
0 4
Sample Output
4
首先在開始正式講解之前我要說，原來除法不一定是下取整的。。。。
比如 1 / 2 = 0
但是-1 / 2 = 0;
所以我們要自己寫上取整和下取整的函數
看到zzy的一個寫法，很不錯,見代碼中的upper和lower
直線可以寫成參數方程的模式
L1: p0 + t * v; t為實數,v 為直線的方向向量
ax + by + c = 0;
首先可以把c移到右邊
ax + by = -c;
知道a,b可以利用擴展歐幾里德公式求出p0和d,(d = gcd(a,b))
如果c不能整除d的話就沒有整數解，這點是顯然的，可以簡單思考一下.
另外通過直線的幾何意義可以知道
v = (b ,-a)或
v = (-b, a)
取其中一個即可
tx = (x - x0)/b;
ty = (y - y0)/-a;
通過兩個去見求出tmin，tmax,之后
ans = tmax - tmin + 1就是結果，如果ans < 0 就是無解
此題破例貼代碼
1
2 LL ans = 0;
3 LL kmin = -300000000000000000LL, kmax = 300000000000000000LL;
4
5 LL ext_gcd(LL a, LL b, LL & x, LL & y)
6 {
7 if (b == 0) {
8 x = 1;
9 y = 0;
10 return a;
11 } else {
12 LL d = ext_gcd(b, a % b, x, y);
13 LL t = x;
14 x = y;
15 y = t - a / b * y;
16 return d;
17 }
18 }
19
20 LL upper(LL a, LL b)
21 {
22 if (a <= 0)
23 return a / b;;
24 return (a - 1) / b + 1;
25 }
26
27 LL lower(LL a, LL b)
28 {
29 if (a >= 0)
30 return a / b;
31 return (a + 1) / b - 1;
32 }
33
34 void update(LL L, LL R, LL a)
35 {
36 if (a < 0) {
37 L = -L;
38 R = -R;
39 a = -a;
40 swap(L, R);
41 }
42 kmin = max(kmin, upper(L, a));
43 kmax = min(kmax, lower(R, a));
44 }
45
46 int main()
47 {
48 LL a, b, c, x1, x2, y1, y2, x0, y0;
49 cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2; // sgu 是ms win,應該用%I64d,我錯了20幾次才發現
.
50 c = -c,ans = 0;
51 if (a == 0 && b == 0) {
52 if (c == 0)
53 ans = (LL) (x2 - x1 + 1) * (y2 - y1 + 1);
54 } else if (a == 0) {
55 LL t = c / b;
56 ans = (c % b == 0 && t <= y2 && t >= y1) * (x2 - x1 + 1);
57 } else if (b == 0) {
58 LL t = c / a;
59 ans = (c % a == 0 && t <= x2 && t >= x1) * (y2 - y1 + 1);
60 } else {
61 LL d = ext_gcd(a, b, x0, y0);
62 if (c % d == 0) {
63 LL p = c / d;
64 update(x1 - p * x0, x2 - p * x0, b / d);
65 update(y1 - p * y0, y2 - p * y0, -a / d);
66 ans = kmax - kmin + 1;
67 if (ans < 0) ans = 0;
68 }
69 }
70 cout << ans << endl;
71 return 0;
72 }
73
74