发布于  更新于 

UVA11768 Lattice Point or Not

exgcd 数论 题解 OI

洛谷水黑题,不过考试的时候把我坑惨了,推了一个半小时都没有推出来,太弱了。。。

题意

在二维坐标系中给定两个点, , , 均为的整数倍,求线段经过多少个格点。

分析

给出的是两点坐标求直线,应该用直线的两点式方程入手。

交叉相乘整理得一般式

求这样的式子的整数解,显然需要exgcd。但是题目给出的是小数,还好只有一位,坐标都扩大十倍。

写代码时不要忘了乘上红色的系数!

然后exgcd常规操作,求出直线上的一个整点

并且其它整点满足

这样求出来的点保证在直线上,我们就不用考虑y坐标,只用管x坐标了。

x坐标上整点出现的周期是,将移动到目标区间开头:

1
int64 xbegin = x + (l - x) / xrep * xrep;

答案就是

1
(r - xbegin) / xrep + 1

代码

注意特判两点式不成立的情况:平行于坐标轴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <cctype>
using namespace std;

typedef long long int64;
const int64 INF = 0x3f3f3f3f3f3f3f3fll;

int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int64 GCD = exgcd(b, a % b, x, y);
int64 tmp = x;
x = y;
y = tmp - a / b * y;
return GCD;
}

inline double dbread() {
double X = 0, Y = 1.0;
int w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) X = X * 10 + (ch ^ 48), ch = getchar();
ch = getchar();
while (isdigit(ch)) X += (Y /= 10) * (ch ^ 48), ch = getchar();
return w ? -X : X;
}

int main() {
int tcnt;
cin >> tcnt;
for (int T = 1; T <= tcnt; T++) {
double x1 = dbread();
double y1 = dbread();
double x2 = dbread();
double y2 = dbread();

int64 X1 = x1 * 10, X2 = x2 * 10, Y1 = y1 * 10, Y2 = y2 * 10;
if (x1 == x2) {
if (X1 % 10 != 0) {
cout << 0 << endl;
} else {
if (y2 < y1) {
swap(y1, y2);
}
cout << floor(y2) - ceil(y1) + 1 << endl;
}
} else if (y1 == y2) {
if (Y1 % 10 != 0) {
cout << 0 << endl;
} else {
if (x2 < x1) {
swap(x2, x1);
}
cout << floor(x2) - ceil(x1) + 1 << endl;
}
} else {
int64 A = (Y2 - Y1) * 10, B = (X1 - X2) * 10;
int64 C = Y2 * X1 - Y1 * X2;
int64 x, y;
int64 GCD = exgcd(A, B, x, y);
if (C % GCD != 0) {
cout << 0 << endl;
} else {
x = x * C / GCD;
int64 xrep = abs(B / GCD);
if (x1 > x2) {
swap(x1, x2);
}
int64 l = ceil(x1);
int64 r = floor(x2);
if (l <= r) {
int64 xbegin = x + (l - x) / xrep * xrep;
if (xbegin < l) {
xbegin += xrep;
}
if (xbegin > r) {
cout << 0 << endl;
} else {
cout << (r - xbegin) / xrep + 1 << endl;
}
} else {
cout << 0 << endl;
}
}
}
}
}