排序与互质handkerchief

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

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

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

如图,假设N为5,首先寻找的是第一个,那么在箭头再次指向1时,2,3,4,5都已经指向过且指向的次数都为1.由此我们可以假设,每一次的指针跨度为a,每跨一次指向一个没有被指向的箱子,一次循环后,共跨了N次,则一次循环共经历了N*a个单位,而在数学上来讲,这正好是最小公倍数的定义,故a与N的最小公倍数为a*N,a与N互质。每次的跨度则是相隔的箱子数目+1,即M。

设a为3的具体图示:

具体代码不予赘述。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目来源HDU - 2104 一道判断互质的题目 The Children’s Day has passed fo...
    敬轩大大阅读 1,175评论 0 0
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,010评论 19 139
  • 第一章数和数的运算 一概念 (一)整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候,用来表示...
    meychang阅读 2,663评论 0 5
  • 总有人会不时的感到孤独,觉得自己身边没有一个可以倾诉的对象。 比如考研的朋友总会感到自己努力的时候是孤独的,没有人...
    一杯酒未消愁阅读 296评论 4 2
  • 使用焚寂打败欧阳少恭后,屠苏也因解封而化为永世不得轮回的“荒魂”,风晴雪为追寻重生之法,携已无剑灵失去上古之威的焚...
    孜雪晴飞阅读 563评论 0 0