首页 > > 程序设计 > C/C++ >

uva11768 Lattice Point or Not

2018-08-14 09:53:37来源：博客园阅读 ()

---恢复内容开始---

比较经典的扩展欧几里德求整数解的问题。

对于两个点(x1,y1)(x2,y2)，如果点为整数点，那么必定能通过扩展欧几里德求出区间中的整点个数,即对方程(y2-y1)x+(x1-x2)y=x1y2-x2y1 求解。

由于此题的点精确到小数后1位，我们可以将x1,y1,x2,y2分别放大10倍，问题转变成对方程[10*(y2-y1)]*x+[10*(x1-x2)]y=100*(x1y2-x2y1)求解。

记a=10*(y2-y1)，b=10*（x1-x2) ，c=100*(x1y2-x2y1), g=gcd(a,b)

那么用扩展欧几里德可以得到aX+bY=gcd(a,b)的一组解。注意，这里得到的一组解仅保证abs(X+Y)取到最小值

判断需要求解的方程是否有解，只需要判断c%gcd(a,b)==0是否成立即可。

那么就可以得到需要求解的方程的一组解：X0=X*c/g, Y0=Y*c/g

此时就可以对区间有几个解进行计算了。

另外，因为之前扩展欧几里德写的少，所以xjb写了一发暴力，此处贴上代码。

正解：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int T;
 5 LL x[2], y[2];
 6 void read(LL &x)
 7 {
 8     LL a, b;
 9     scanf("%lld.%lld", &a, &b);
10     x = a * 10 + b;
11 }
12 void exgcd(LL a, LL b, LL& g, LL& x, LL& y)
13 {
14     if (!b) g = a, x = 1, y = 0;
15     else exgcd(b, a%b, g, y, x), y -= x * (a / b);
16 }
17 LL solve()
18 {
19     LL ans = 0;
20     for (int i = 0; i < 2; i++)read(x[i]), read(y[i]);
21     if (x[0] > x[1] || x[0] == x[1] && y[0] > y[1]) {
22         swap(x[0], x[1]);
23         swap(y[0], y[1]);
24     }
25 
26     if (x[0] == x[1]) {
27         if (x[0] % 10)return 0;
28         return max(0LL, y[1] / 10 - (y[0] + 9) / 10 + 1);
29     }
30     if (y[0] == y[1]) {
31         if (y[0] % 10)return 0;
32         return max(0LL, x[1] / 10 - (x[0] + 9) / 10 + 1);
33     }
34 
35     LL a, b, g, X, Y;
36     a = (y[1] - y[0]) * 10;
37     b = (x[0] - x[1]) * 10;
38     exgcd(a, b, g, X, Y);
39     LL c = x[0] * y[1] - x[1] * y[0];
40     if (c%g)return 0;
41     X = X * c / g;
42     x[0] = (x[0] + 9) / 10;
43     x[1] = x[1] / 10;
44     if (x[0] > x[1])return 0;
45     LL st = abs(b / g);
46     LL cx = X - (X - x[0]) / st * st;
47     if (cx < x[0])cx += st;
48     if (cx > x[1])return 0;
49     return (x[1] - cx) / st + 1;
50 }
51 int main()
52 {
53     //freopen("in.txt", "r", stdin);
54     //freopen("out.txt", "w", stdout);
55     scanf("%d", &T);
56     while (T--) {
57         printf("%lld\n", solve());
58     }
59 }

View Code

暴力：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL ;
 4 int T;
 5 LL x[2], y[2];
 6 LL gcd(LL a, LL b)
 7 {
 8     return b == 0 ? a : gcd(b, a%b);
 9 }
10 void read(LL &x)
11 {
12     LL a, b;
13     scanf("%lld.%lld", &a, &b);
14     x = a * 10 + b;
15 }
16 int main()
17 {
18     scanf("%d", &T);
19     while (T--) {
20         for (LL i = 0; i < 2; i++)read(x[i]), read(y[i]);
21         /*for (int i = 0; i < 2; i++) {
22             x[i] = (rand() % 200 + 1) * 10;
23             y[i] = (rand() % 200 + 1) * 10;
24         }*/
25         //printf("%d %d %d %d\n", x[0], y[0], x[1], y[1]);
26         if (x[0] > x[1] || x[0] == x[1] && y[1] > y[0]) {
27             swap(x[0], x[1]);
28             swap(y[0], y[1]);
29         }
30         if (x[0] == x[1] && (x[0] % 10) || y[0] == y[1] && (y[0] % 10)) {
31             printf("0\n");
32             continue;
33         }
34         if (x[0] == x[1] && y[0] == y[1]) {
35             if (x[0] % 10 == 0 && y[0] % 10 == 0) {
36                 printf("1\n");
37             }
38             else printf("0\n");
39             continue;
40         }
41         LL dx = abs(x[0] - x[1]);
42         LL dy = abs(y[0] - y[1]);
43         LL g = gcd(dx, dy);
44         LL st = dx / g;
45         LL cx = x[0], cy = y[0];
46         LL ans = 0;
47         for (LL i = 0; i <= 100 && cx <= x[1] && (cy - y[0])*(cy - y[1]) <= 0; i++) {
48             if (cx % 10 == 0 && cy % 10 == 0) {
49                 long long gc = gcd(gcd(st, 10), gcd(dy / g, 10));
50                 LL t = 10 / gcd(gcd(st, 10), gcd(dy / g, 10));
51                 if (st)ans = 1 + (x[1] - cx) / (t*st);
52                 else ans = abs(y[1] - cy) / (dy / g * t) + 1;
53                 break;
54             }
55             cx += st;
56             cy += (y[1] - y[0]) / g;
57         }
58         printf("%lld\n", ans);
59     }
60 }