程序员的算法趣题Q03: 翻牌

1.问题描述

有100张写着数字1~100的牌，并按顺序排列着。最开始所有牌都是背面朝上放置。某人从第2张牌开始，隔一张牌翻牌。然后第2，4，。。。100张牌就会翻为朝上。接下来，第2个人从第3张牌开始，每隔2张牌翻一张；第3个人从第4张牌开始，每隔3张牌翻一张；。。。这样一直继续下去，直到最后没有牌可翻了。

请问，最终所有背面朝上的牌的数字。

2.解题思路

这是一道有名相当于小学高年级或初中低年级的奥数竞赛级别的数学趣味题。

因为初始状态是背面朝上，所以最终仍然背面朝上的牌一定是经过了偶数次（0，2，4，。。。）翻转。

站在第m张牌的角度来看，在第k轮（即从第k+1张牌开始每隔k张翻一张）翻牌中，只有当m能够被k整除（代数中通常记为）时，第m张牌才会被翻转。这就意味着，第m张牌如果在最终是背面朝上，则必然是有偶数个除1以外的因子（含自己）。

由初等数论的知识可知，一个整数在进行因数分解时，其因子是成对出现的（比如说8的因子，有2和4是一对，1和8是一对），只有一种情况例外，即该数是完全平方数，比如说，此时m作为n的因子是单独出现（它与自己成对，只能算做一个）。所以，一个整数只有在它是完全平方数的时候，才会有总共（含1和自己）奇数个因子，也即除1以外有偶数个因子。

基于以上分析，可以直到，最终仍然保持背面朝上的牌的序号必然是完全平方数。因此本题转变成了求100以内的完全平方数，答案也就显而易见恰好1~10的平方：1,4,9,16,25,36,49,64,81,100