解决ACM算法经典例题：狼与兔子的平安洞判断

本题是一道ACM（算法竞赛）的经典问题，题目名为"狼与兔子"（Wolf and Rabbit），属于数论领域中的一个有趣问题。该问题主要考察对数的模运算以及周期性的理解。以下是详细的解题分析： **题目描述：** 题目设定在一个有n个洞（0到n-1）的山上，其中n由用户输入。兔子需要选择一个洞躲藏，而狼会按照逆时针顺序搜索。搜索规则是：首先狼进入标记为0的洞，接着每次跳过m个洞后进入下一个，形成一个循环。例如，当m=2且n=6时，搜索路径为0,2,4,0（形成一个长度为4的循环）。如果兔子藏在编号为1,3或5的洞里，即非安全洞穴，它就能避开狼。相反，如果存在安全洞穴，意味着狼不能覆盖所有洞穴，输出"YES"；反之，输出"NO"。 **输入和输出格式：** - 输入包含一个整数P，表示有P组测试数据。 - 每组数据包括两个正整数m和n，满足0<m,n<2147483648，表示狼跳跃的间隔和洞的数量。 - 对于每组数据，你需要判断是否存在安全洞穴，输出"YES"或"NO"。 **关键思路与方法：** 1. **判断周期性**： - 当m和n的关系使得狼的搜索路径形成一个完整的循环时，即m能够整除n，狼会访问每个洞至少一次，没有安全洞。在这种情况下，输出"NO"。 - 如果m不能整除n，那么狼的搜索路径不会形成一个完整循环，必定会有部分洞穴未被访问，存在安全洞穴，此时输出"YES"。 2. **模运算的应用**： - 使用取模运算（%）可以帮助简化判断过程。计算m除以n的余数r，若r不等于0，说明m和n存在非零余数，这意味着不是所有洞都被访问，有安全洞。 3. **优化处理**： - 避免直接枚举所有可能的m值，而是用取模的方式快速判断，提高代码执行效率。 例如，当分析m=4和m=5的情况时，我们发现m=4形成的循环为0,4,2,0，显然可以覆盖所有洞；而m=5形成的循环为0,5,4,3,2,1,0，此时每个洞都被访问，不存在安全洞。这说明，判断安全洞的关键在于m是否能整除n，或者是否有一个非零余数r。 总结来说，解决这个问题的关键在于理解数论中的周期性和取模运算在算法中的应用，以及如何利用这些概念来判断是否存在安全洞穴。对于给定的测试数据，通过计算并比较m和n的关系，就可以得出相应的输出结果。