2009年11月25日星期三.sgu106
這題終于過(guò)了......
太容易錯(cuò)了
忘了sgu是ms win,用%lld錯(cuò)了十幾次，干脆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
首先在開始正式講解之前我要說(shuō)，原來(lái)除法不一定是下取整的。。。。
比如 1 / 2 = 0
但是-1 / 2 = 0;
所以我們要自己寫上取整和下取整的函數(shù)
看到zzy的一個(gè)寫法，很不錯(cuò),見代碼中的upper和lower
直線可以寫成參數(shù)方程的模式
L1: p0 + t * v; t為實(shí)數(shù),v 為直線的方向向量
ax + by + c = 0;
首先可以把c移到右邊
ax + by = -c;
知道a,b可以利用擴(kuò)展歐幾里德公式求出p0和d,(d = gcd(a,b))
如果c不能整除d的話就沒有整數(shù)解，這點(diǎn)是顯然的，可以簡(jiǎn)單思考一下.
另外通過(guò)直線的幾何意義可以知道
v = (b ,-a)或
v = (-b, a)
取其中一個(gè)即可
tx = (x - x0)/b;
ty = (y - y0)/-a;
通過(guò)兩個(gè)去見求出tmin，tmax,之后
ans = tmax - tmin + 1就是結(jié)果，如果ans < 0 就是無(wú)解
此題破例貼代碼
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,應(yīng)該用%I64d,我錯(cuò)了20幾次才發(fā)現(xiàn)
.
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