2014-03-20 01:14
题目：有100栈灯，一开始都关着。如果你按照n从1~100的顺序，每次都掰一下n的倍数的开关(开->关，关->开)，那么到最后有多少灯是亮的？
解法：这个题目要多想想再动手，因为想通了以后就基本不用动手了。对于编号为x的灯，每当i是x的约数时，在第i轮时第x号灯就被掰了一次。比如6的约数为{1,2,3,6}，6号灯被掰了4次。那么，每个灯被掰的次数就是约数个数次。约数个数的公式你懂的，但是用不着去算。如果一盏灯是开的，那么它就被掰了奇数次，根据约数和公式，只有因数分解之后所有指数都是偶数的时候，约数个数才为奇数。比如36的约数{1,2,3,4,6,9,12,18,36}。只有完全平方数满足条件。还有另一种想法，如果一个数n不是完全平方数，那么n的约数一定可以分为个数相同的两拨儿，一拨儿大于平方根，一拨儿小于平方根，配对正好成绩等于n。只有完全平方数才会多出一个整数的平方根，导致约数个数为奇数。
代码：
// 6.6 Given n lights, every time you toggle the switches of k-multiples. k goes from 1 to n.
// Assume they're all off at first, how many of them are on at last.
#include <cstdio>
using namespace std; // My solution:
// For a number m between 1~n, the key is total number of divisors of m, defined as num_div(m).
// The light m is toggled for num_div(m) times. If it is odd, light is on. Even and light is off.
// Only perfect square can be factorized, where every prime factor has even exponents.
// That is, m = p[0]^e[0] * p[1]^e[1] * ... * p[whatever]^e[whatever]
// num_div(m) = (e[0] + 1) * (e[1] + 1) * ... * (e[whatever] + 1)
// If num_div(m) is to be odd, every multiplier has to be odd, every e[i] has to be even.
// Thus m has to be a perfect square, if light m is on at last.
int main()
{
int n;
int i; while (scanf("%d", &n) == && n > ) {
for (i = ; i <= n / i; ++i) {
printf("%d ", i * i);
}
printf("\n");
printf("%d light(s) is(are) on.\n", i - );
} return ;
}