97^{59}
除以59的余数是多少解:
97^{59} \equiv 97 \qquad (mod \quad 59)费马小定理:假设a是一个整数, p是一个素数,那么
a^{p}\equiv a \qquad (mod \quad p)2. 两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。
下面是偶的思路。
这是一个很典型的动态规划问题。用确定minNum[n]表示鸡蛋从高n层的楼摔下不碎需要的最小次数。则有
转移方程:
minNum[n] = min(1 + max(i–1, minNum[n-i]))
1<=i<=n
边界条件:
minNum[0] = 0; minNum[1] = 1
假设i是第一次扔鸡蛋的楼层,如果破了,则为了确定下面楼层中的安全位置,需要从第一层挨着试,需要i-1次,不碎的话上面还有n-i层,还剩两个鸡蛋,需要minNum[n-i]次。
3. 有一个村庄,村庄里各户人家直到生出女孩来就不再生小孩了,而生男孩女孩的概率各是1/2。请问这个村庄男孩女孩的比例是多少?
解:
生一个:则为女孩,概率为1/2
生二个:则第一个为男,第二个为女,概率为1/2 * 1/2
...
生n个:则前n-1为男,最后一个为女,概率为
\frac{1}{2^{n-1}} \time \frac{1}{2}生男孩的个数为
0 \time \frac{1}{2} + 1 \time \frac{1}{2^2} + \dots (n-1) \time \frac{1}{2^{n}} 4. 3. 实验室里有1000个一模一样的瓶子,但是其中的一瓶有毒。可以用实验室的小白鼠来
测试哪一瓶是毒药。如果小白鼠喝掉毒药的话,会在一个星期的时候死去,其他瓶子里
的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药
a. 9 b. 10 c. 32 d. 999
e. 以上都不对
