欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

uva11768 Lattice Point or Not

程序员文章站 2022-06-30 18:30:36
恢复内容开始 比较经典的扩展欧几里德求整数解的问题。 对于两个点(x1,y1)(x2,y2),如果点为整数点,那么必定能通过扩展欧几里德求出区间中的整点个数,即对方程(y2-y1)x+(x1-x2)y=x1y2-x2y1 求解。 由于此题的点精确到小数后1位,我们可以将x1,y1,x2,y2分别放大 ......

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

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

对于两个点(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写了一发暴力,此处贴上代码。

正解:

uva11768 Lattice Point or Not
 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

暴力:

uva11768 Lattice Point or Not
 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 }
View Code

 

---恢复内容结束---