题目描述
Link
Solution
通过观察，我们可以发现，如果两个位置之间有完整的墙挡住时，那么这两个位置就不能互相到达。
再观察，我们又可以发现，这个东西和最大公约数有关。
因此我们可以设 $g=\gcd(n,m)$，把一号区域分成大小为 $\frac{n}{g}$ 的块，把二号区域分成大小为 $\frac{m}{g}$ 的块，每层区域块的个数都是 $g$。
然后判断这两个位置所在块的编号是否相同就行了。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
ll n, m, a, b, g, f[3];
int x, y, q;
template <typename T>
T gcd(T a, T b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
int main() {
scanf("%I64d%I64d%d", &n, &m, &q);
g = gcd(n, m);
f[1] = n / g;
f[2] = m / g;
while (q--) {
scanf("%d%I64d%d%I64d", &x, &a, &y, &b);
if ((a / f[x] + ((a % f[x]) != 0)) != (b / f[y] + ((b % f[y]) != 0))) puts("NO");
else puts("YES");
}
}
|
