acm算法经典例题
79页1、一、数论1: Wolf and Rabbit描述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.输入The input starts
2、 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(0m,n2147483648).输出For each input m n, if safe holes exist, you should output YES, else output NO in a single line.样例输入21 22 2样例输出NOYES翻译:描述一座山有n个洞,洞被标记为从0到n-1。兔子必须藏在一个洞中。狼会逆时针方向搜索兔子。狼一开始在洞0,然后他会每m个洞进去一次。例如:m=2,n=6,狼就会依次进入洞0 2 4 0。如果兔子藏在1 3 5就安全。输入第一行一个数字p,表示下面有p组测试数据,每组测试数据2个数m n(0m,n2147483648)输出每组数据输出一行,如果存在安全洞穴,输出YES,否则输出NO思路/方法:你是不是觉得总是无法通过,看看下面的解析假
3、设有n=6个洞 0 1 2 3 4 5当m=4时,狼进的洞是0 4 2 0,也就是形成了一个循环,永远也到不了其他洞穴当m=5时,狼进的洞是0 5 4 3 2 1 0,这时所有的洞都遍历了一遍。思考:当m=4和m=5时,到底有什么区别?当n和m有公约数(非1)时,就会形成一个数字个数小于n的循环当n和m无公约数时,就会形成一个数字个数为n的循环,此时没有安全洞穴。解题关键:这题就转化成了判断两个数是否有公约数。代码:#include using namespace std;long long greatestCommonDivisor(long long a, long long b)/最大公约数 long long t; while(b) t = a % b; a = b; b = t; return a;int main() int i, p; long long m, n; cin p; for(i = 0; i m n; if(greatestCommonDivisor(m, n) = 1)/公约数为1说明互斥,没有安全洞穴 cout NOn; else cout YESn;
《acm算法经典例题》由会员小**分享,可在线阅读,更多相关《acm算法经典例题》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-04-08 33页
2024-04-08 10页
2024-04-08 25页
2024-04-08 12页
2024-04-08 10页
2024-04-08 21页
2024-04-08 40页
2024-04-08 34页
2024-04-08 28页
2024-04-08 28页