HDU 1222 Wolf and Rabbit(gcd)
发布日期:2021-08-21 13:17:43 浏览次数:30 分类:技术文章

本文共 1558 字,大约阅读时间需要 5 分钟。

HDU 1222   Wolf and Rabbit   (最大公约数)解题报告

题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88159#problem/G

题目:

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
 
题意:
山周围有从0~n-1的n个山洞,狼按逆时针的顺序抓兔子,判断兔子是否能活下来。
 
分析:
这是一个求最大公约数的问题。可以用书上的gcd算法--辗转相除法。gcd(a,b)=gcd(b,a%b),还要考虑它和边界条件gcd(a,0)=a。
 
代码:
1 #include
2 #include
3 using namespace std; 4 5 int gcd(int a,int b)//辗转相除法 6 { 7 return b==0?a:gcd(b,a%b); 8 } 9 10 int main()11 {12 int p;13 int m,n;14 scanf("%d",&p);15 while(p--)16 {17 scanf("%d%d",&m,&n);18 gcd(m,n);19 if(gcd(m,n)==1)20 printf("NO\n");21 else22 printf("YES\n");23 }24 return 0;25 }

 

转载于:https://www.cnblogs.com/ttmj865/p/4746364.html

转载地址:https://blog.csdn.net/weixin_33720078/article/details/93654311 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:脱离标准文档流(1)---浮动
下一篇:gprof

发表评论

最新留言

很好
[***.229.124.182]2024年03月13日 16时40分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

郑州大学c语言课程设计2000行,C语言课程设计大作业(1).pptx 2019-04-21
Android5.1自定义闹钟铃声,Android 设置来电铃声、通知铃声、闹钟铃声中的坑 2019-04-21
android 程序更换字体,Android修改自己程序字体的方法详解 2019-04-21
c语言4x4矩形列互换,线反转法4x4键盘C语言程序问题.急... 2019-04-21
android服务开启线程,android之service与intentService的不同 2019-04-21
android 6.0 蓝牙进程,Android6.0-蓝牙权限问题 2019-04-21
wxml修改样式_[笔记]小程序支持的样式选择器 2019-04-21
banner 获取当前指示物_学会这些技巧,让你的banner脱颖而出 2019-04-21
线上banner什么意思_广交会线上直播怎么做 2019-04-21
获取默认值_TarsGo 服务获取自定义模版(配置)值 2019-04-21
启动rocketmq_rocketmq 部署启动指南-Docker 版 2019-04-21
热敏打印_热敏打印机需要碳带吗? 2019-04-21
点击屏幕触发_Flutter 中文文档:点击、拖动和其他手势 2019-04-21
怎么解决_壁挂炉出现e2是怎么回事?一般怎么解决? 2019-04-21
内容换行_内容换行或分段不会影响到SEO优化和搜索引擎收录抓取 2019-04-21
图形化分析工具_酷炫!一款 Go 语言实现的实时图形化分析的性能测试工具 2019-04-21
发动机冷启动和热启动的区别_柴油发动机冬季启动3招小窍门 2019-04-21
怎样将图片弄成白底的_做跨境电商想拍出爆款产品图片,我只用这五招 2019-04-21
苹果手机如何分享安装包_苹果手机显示 Apple ID 被停用该如何恢复? 2019-04-21
python采用单例模式游戏_Python单例模式(Singleton)的N种实现 2019-04-21