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