2009年5月15日金曜日

一道小学奥数题【兵马俑】

466个6能不能被13整除?
【同情一下小学生咩】

因为1001=13×99,所以1001可以被13整除,继而我们有6006可以被13整除,60060可以被13整除,600600可以被13整除。以上三者之和为666666,当然也可以被13整除。继而,12个6可以被13整除因为666666666666=666666000000+666666。以此类推,6的倍数个6都可以被13整除。

466除以6余4,我们把高位的6去掉,剩下6666,再减去6006,剩下660,再用13除,这个我就想不到什么办法了,硬算也不难了,我们有660除以13等于50余10,故原数不能被13整除,余数是10。

本题基于一些同余的理论,但理解起来并不难,至于1001=13×99,很久之前有看过这个性质。还有37×3=111,都是经常被用来出题的。


据说小学有专门的算法的,很简单
后三位减去相邻前三位能被13整除,那这六位就能被13整除
所以666666:666-666=0,666666可以被13整除
所以466mod6=4,最前4位为6666,:666-6=660
660不被13整除,所以不能整除

2009年5月12日火曜日

Beyond 1993 in Malaysia Unplugged live

“真的爱你”,best version in my mind

how to judge A*B == C?

Three matrix A,B,C, how to measure if A*B equals C in O(n^2)?
//*
一个基于概率的算法是随机生成一个n乘1的矩阵R,然后判断A*B*R是否等于C*R,而前者相当于A*(B*R),与后者一样都可以在O(n^2)的时间里算出来。如果算出来的结果相等,几乎可以肯定A*B和C也是相等的。
*/