删帖吧

benjiam

这道貌似是 M$ 的题目

benjiam

分析
一下 一个数 在 1  本身  以及可以分解成质因子的时候

都会改变

所以 1  可以。

质数 不可以 因为被改变2次

第三 可以被分解成 奇数个质因子相乘的也可以

首先 被分解成质子 相同的可以

1×1
2×2
3*3
....
6 ×6  

1 2 3 6 12

可以的


8 × 8

1 2 4 8  16

可以



9*9 不行  9 可以继续分

1 3 9 27 81
还是可以



10* 10
10×10 不行 10 可以继续分


结果就是分解一个整数 求出所有的质因子  奇数的可以 偶数的不行


平方数可以



还是无法证明 为什么完全平方数可以

liexusong

完全平方数
ps 记得在小学奥数中看到过
mike79 发表于 2010-06-22 19:10

    哦!想不到小学的已经有这么难的题目啊!

mgqw

中国的奥数就是一个变态的东西

mgqw

除了变态还有畸形。
完全偏离了最初的本质。

lycusual

这道貌似是 M$ 的题目
benjiam 发表于 2010-06-24 09:01

确实是MS的，我去面试的时候被出的也是这么一道。

狗气球

回复 32# benjiam


    想复杂了。这题目和质数没关系。

xyfree

回复 37#
狗气球



    口胡，谁说和素数没有关系？？


如果灯的编号N是一个素数，因为素数只有1和他本身这两个因数，所以整个过程中只会被开关两次，于是就会灯灭；

如果等的编号N是一个合数，那么这个合数可能有三种素因数分解的形式，下式中p1,p2..pn代表不同的素数

1. N=p1*p2*....*pn 也就是这个合数N刚好等于n个不同素数的1次幂的乘积。那么这个素数的所有因数，必然都是从这n个素数中抽取0到n个相乘。
即因数数f(N)=C(n,0)+C(n,1)+...+C(n,n)=2^n，因此必定是一个偶数，灯灭；

2：N=s1*s2...*sn，其中si=pi^(2k)，就是说，N刚好是一个完全平方数，那么其必然可以分解成若干个不同素数的偶次幂再乘积。
对于每个形如si=pi^(2k)的项，其因数数
f(si)=C(2k,2)+C(2k,4)...+C(2k,2k)
=2^(2k-1)+1 必然是奇数，于是f(N)=f(s1)*f(s2)*...*f(sn) 也必然是奇数。灯亮


3：N=p1^k1 * p2^k2 * ... *pn^kn
,其中k1...kn不全为1，那么这个合数的素因数分解必然可以改写成以下的形式：
N=N1 * N2
其中N1=pi1*pi2*...*pin，N2=s1*s2*...*si
i1...in 是k1...kn为奇数的项，s1...si是若干个不同素数的偶次幂。

由1,2结论知，此时f(N)的值为一个偶数乘以一个奇数，还是一个偶数，灯灭。

综上，编号恰好为完全平方数的等是亮的，即编号为1,4,9,16,25,36,49,64,81,100的灯是亮的

狗气球

灯灭的条件是有偶数个因数。
仅此而已。
考虑是否质数已经多余了。

你当然可以说，因为所有的质数都有偶数个因数，所以这题目和质数有关系。那我也没辙。
绝大多数合数也有偶数个因数呢。

我当初做这个题目的时候也曾经习惯性的从质数开始分析，想清楚之后就觉得和质数没关系，因数分解而已。

xyfree

回复 39# 狗气球


    可是你要证明完全平方数的因数个数是奇数，就不得不利用素数来证明。
    难道这样还可以说是没有关系？