侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【数学】兔八哥与猎人

GabrielxD
2023-09-26 / 0 评论 / 0 点赞 / 163 阅读 / 1,314 字
温馨提示:
本文最后更新于 2023-09-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1170 兔八哥与猎人


题目描述

兔八哥躲藏在树林旁边的果园里。果园有 M×NM \times N 棵树,组成一个 MMNN 列的矩阵,水平或垂直相邻的两棵树的距离为 11。兔八哥在一棵果树下。

猎人背着猎枪走进了果园,他爬上一棵果树,准备杀死兔八哥。

如果猎人与兔八哥之间没有其它的果树,猎人就可以看到兔八哥。

现己知猎人和兔八哥的位置,编写程序判断兔子所在的位置是否安全.

输入格式

第一行为 nn,表示有 nn 组数据,每组数据的第一行为两个正整数 axa_xaya_y,表示猎人的位置,第二行为两个正整数 bxb_xbyb_y,表示兔八哥的位置。

输出格式

共有 nn 行,每行为 yesno 表示兔八哥的位置是否安全。

样例 #1

样例输入 #1

1
1 1
1 2

样例输出 #1

no

提示

1n1051\le n \le 10^51ax,ay,bx,by1081 \le a_x, a_y, b_x, b_y \le 10^8

解题

方法一:数学

思路

一开始我以为只要检查猎人周围的八个点,如果兔八哥没在这八个点中就说明位置安全,但在 WA 了一次之后发现:只有两点连成的线段之间(不包括线段两端)不存在整数点时,位置才算得上是安全,例如下图:

image-20230926170753401

假如猎人与兔八哥的坐标分别为:(ax,ay),(bx,by)(a_x, a_y), (b_x, b_y),那么当 axbx|a_x-b_x|ayby|a_y - b_y| 不互质时(即 gcd(axbx,ayby)1\gcd(|a_x-b_x|, |a_y - b_y|) \ne 1),则这两点连成的线段上(不包括线段两端)必定存在至少一个整数点。具体证明如下(Generated by ChatGPT(GPT-3.5)):

首先,我们可以通过反证法来证明这个陈述。假设有两个整数点 (ax,ay)(a_x, a_y)(bx,by)(b_x, b_y),它们满足 axbx|a_x - b_x|ayby|a_y - b_y| 不互质。这意味着它们有一个共同的因子,即存在一个整数 dd,使得 d>1d > 1dd 同时整除 axbx|a_x - b_x|ayby|a_y - b_y|

现在考虑点 (ax,ay)(a_x, a_y)(bx,by)(b_x, b_y) 之间的线段。我们可以将这条线段看作是从 (ax,ay)(a_x, a_y) 出发,朝着 (bx,by)(b_x, b_y) 移动的过程。我们可以在该线段上选择一个整数点,该点的坐标可以表示为 (x,y)(x, y),其中 xxyy 分别表示在 xxyy 方向上移动的步数。我们可以用以下方式计算 xxyy

  1. 计算 xx:我们知道 axbx|a_x - b_x| 可以被 dd 整除,因此存在整数 kk,使得 axbx=kd|a_x - b_x| = kd。那么我们可以写出:
    x=ax+ktx = a_x + kt,其中 tt 是一个整数。

  2. 计算 yy:同样地,ayby|a_y - b_y| 可以被 dd 整除,存在整数 ll,使得 ayby=ld|a_y - b_y| = ld。那么我们可以写出:
    y=ay+lty = a_y + lt,其中 tt 是一个整数。

现在,我们看到 (x,y)(x, y) 的坐标是由 tt 决定的,而 tt 可以是任何整数。这意味着我们可以在该线段上选择一个整数点 (x,y)(x, y),因为我们可以选择适当的整数 tt 使得 (x,y)(x, y) 的坐标都是整数。因此,该线段上至少存在一个整数点,证明了原陈述的正确性。

代码

#include <cstdio>
#include <cmath>

using namespace std;

int n, ax, ay, bx, by;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d%d%d", &ax, &ay, &bx, &by);
        puts(gcd(abs(ax - bx), abs(ay - by)) != 1 ? "yes" : "no");
    }

    return 0;
}

参考

0

评论区