E-jwMM的射箭游戏

E-jwMM的射箭游戏

/ 0评 / 1336次 / 0

Description

jwMM和她的好朋友GG一起在公园里散步的时候,眼前突然出现了一个悬浮的箭靶,jwMM马上拿出了自己藏在身上的弓,准备射中箭靶,向好朋友炫耀。但是她的好朋友GG知道jwMM的弓术无比差劲,就决定用念力帮她维护一下她脆弱的自尊心。现在给出箭靶的坐标x1,y1,jwMM射出的箭被念力包裹时的坐标x2,y2,如果x2-y2恰好是x1与y1的某个大于1的公因子的正整数倍,则可以射中,否则就射不中。 请判断最后jwMM是否能够射中靶子,如果能,输出Y,否则输出N。

Input

多组输入。 每组输入四个整数x1,y1,x2,y2。 x1,y1代表箭靶的坐标,x2,y2代表箭被念力包裹时的坐标。 保证所有输入数据为正且在int范围之内。

Output

输出Y或N。

Analysis

题目就是要求一个数a是否是数b的某个大于1的因子的正整数倍。

一开始我将b的所有因子一次获取比较,发现会超时

再优化可以知道,我们要找的这样一个因子c满足a%c==0, b%c==0

可以发现,这样的c相当于a和b的某一公因子,而快速判断这样一个不为1的公因子是否存在,即是判断a和b的最大公因子是否为1,如果不为1才存在这样的一个公因子,反之则不存在

Accepted Code

/*
 * @Author: Gehrychiang
 * @LastEditors: Gehrychiang
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x1, x2, y1, y2;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        int flag = 1;
        int a = x2 - y2;
        int b = __gcd(x1, y1);
        if (a <= 0) //特判不可能
        {
            flag = 0;
        }
        if (b == 1) //特判不可能之二
        {
            flag = 0;
        }
        //找到一个数c c*m=b  c*n=a
        int c = __gcd(a, b);
        if (c > 1 && flag == 1)
        {
            cout << "Y" << endl;
        }
        else
        {
            cout << "N" << endl;
        }
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63970