c++ - 【acm】关于完整遍历一个圈中所有点的问题，确定间隔和圈上点的个数，为什么判断gcd（m,n） == 1 就可以判断遍历完整?

Question

兔子的烦恼(一）
时间限制：1000 ms | 内存限制：65535 KB
描述
在一座山上有n个山洞（每个洞从0~n-1分别编号），这山上有一只兔子躲在山洞里，有一只狼，从编号为0的山洞开始入洞，每隔m-1个洞，再次入洞抓兔子，现在问，兔子能否避免这场灾难？
例如：m=2 and n=6, 狼将要进入的山洞号为：0,2,4,0;
输入
有多组测试数据，不超过1000组;

每组有两个整数m,n(0<m,n<=1000);
注意：程序以文件结束符“EOF”结束输入。
输出
兔子能避免这场灾难输出YES，否则输出NO;
样例输入
1 2
2 2
样例输出
NO
YES

Answer 1

2 つの数値が互いに素でない場合、それらの数値には共通因数 $k$ があり、$n = ak、m = bk$ が存在することがわかり、可能な位置はすべて $cndm = になるはずです。 cak - dbk = k (ca - bd) $ は、すべての可能な位置がこの共通因数 $k$ の倍数でなければならないことを知ることができます。もちろん、すべての場所を通過できるわけではありません。
2 つの数値が互いに素である場合、ここでの $k$ は 1 であり、明らかにすべての位置をたどることができます。