排序与互质handkerchief

最近暑假在家里做ACM试题时，看到了这道有趣的题目；题目的大致意思如下：

haha从N个箱子里找手帕，每一次他都隔M-1个箱子找，求他最后能不能找到手帕。在百度上搜到了这个问题的解决方法是求M和N是否互质，而对于为什么用互质的方法求却没有详细的说明。

这Ｎ个箱子是排成一个圆圈的，能找到手帕的结果是当ｈａｈａ第二次打开最开始打开的第一个箱子时其余的全部箱子都已经打开过了。

如图，假设Ｎ为５，首先寻找的是第一个，那么在箭头再次指向１时，２,３,４,５都已经指向过且指向的次数都为１.由此我们可以假设，每一次的指针跨度为ａ，每跨一次指向一个没有被指向的箱子，一次循环后，共跨了Ｎ次，则一次循环共经历了Ｎ＊ａ个单位，而在数学上来讲，这正好是最小公倍数的定义，故ａ与Ｎ的最小公倍数为ａ＊Ｎ，ａ与Ｎ互质。每次的跨度则是相隔的箱子数目＋１，即Ｍ。

设ａ为３的具体图示：

具体代码不予赘述。