转化为用欧几里得算法判断互质的问题D - Wolf and Rabbit

时间：2015-10-17 22:02:06 阅读：334 评论：0 收藏：0 [点我收藏+]

Description

There is a hill with n holes around. The holes are signed from 0 to n-1.

技术分享

A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.

Input

The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,each line consists 2 positive integer m and n(0<m,n<2147483648).

Output

For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line.

Sample Input

2 1 2 2 2

Sample Output

NO YES

问题描述：一只狼在一个环形的路上走，环形路总共有n个洞，狼从起点开始每隔m个洞进洞搜索一次，问有没有安全的洞

　　　　　有输出YES,否则输出NO

思路：判断m和n是否互质，互质则不存在安全的洞，否则就存在安全的洞

　　　　原因：

　　　　　　　　m和n的最小公倍数T = m*i = n*j; 走的距离为T的时候狼又回到原点，开始下个周期的搜索，每个周期所遍历的洞一样

　　　　　　　假设走了T这么长的距离还没把所有洞搜索完一定搜索不到了，因为接下来搜索到的地方和原来肯定是重复的

　　　　　　　m和n互质的时候刚好T=m*n，一个周期，刚好遍历n个洞

　　　　　　　如果m和n不互质，那么i肯定小于n，也就是说遍历i( 小于m次)就够一个周期了，肯定不能便利完n个洞啊

　　　　　　　只有当m和n互质的时候，狼在一个周期内才能搜索完所有的洞

其实判断互质很简单，关键是能不能想到这道题实际上是一道判断互质的问题

#include <stdio.h>
#define LL long long
LL gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a%b);
}
int main()
{
    bool flag; 
    LL t;
    scanf("%lld", &t);
    while(t--)
    {
        LL m, l;
        flag = 1;
        scanf("%lld%lld", &m, &l);
        if(gcd(m, l) == 1)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

转化为用欧几里得算法判断互质的问题D - Wolf and Rabbit

原文：http://www.cnblogs.com/rain-1/p/4888149.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)