Project Euler解题汇总(更新至309在1楼)

sir.liang

只能看到110

tree_new_bee

原帖由 〇〇 于 2011-1-8 07:07 发表
从108楼挑出1个难度适中的
71   2  比3/7小且分子分母均不大于1000000的最简 枚举分母，由于分子递增，可以维护一个指针，  428570
         分数中，最接近3/7的分数的分子是多少？           总复杂度O(N)。计算差之后更新答案即可。

又是循环小数
3/7=0.(428571)
=428571/999999
所以...

这个做法非常棒!

不过， 你怎么知道如果428571/999999>=3/7的话， 428570作为分子就一定能有一个满足条件的分母？

〇〇

Problem 320
15 January 2011


Let N(i) be the smallest integer n such that n! is divisible by (i!)1234567890

Let S(u)=∑N(i) for 10≤i≤u.

S(1000)=614538266565663.

Find S(1 000 000) mod (10^18)

〇〇

Problem 318
01 January 2011

Consider the real number √2+√3.
When we calculate the even powers of √2+√3 we get:
(√2+√3)^2 = 9.898979485566356...
(√2+√3)^4 = 97.98979485566356...
(√2+√3)^6 = 969.998969071069263...
(√2+√3)^8 = 9601.99989585502907...
(√2+√3)^10 = 95049.999989479221...
(√2+√3)^12 = 940897.9999989371855...
(√2+√3)^14 = 9313929.99999989263...
(√2+√3)^16 = 92198401.99999998915...


It looks like that the number of consecutive nines at the beginning of the fractional part of these powers is non-decreasing.
In fact it can be proven that the fractional part of (√2+√3)^2n approaches 1 for large n.

Consider all real numbers of the form p+q with p and q positive integers and pq, such that the fractional part of (p+q)^2n approaches 1 for large n.

Let C(p,q,n) be the number of consecutive nines at the beginning of the fractional part of
(p+q)^2n.

Let N(p,q) be the minimal value of n such that C(p,q,n) ≥ 2011.

Find ∑N(p,q) for p+q ≤ 2011.




Let N(p,q) be the minimal value of n such that C(p,q,n) ≥ 2011.

Find ∑N(p,q) for p+q ≤ 2011.

[ 本帖最后由 〇〇 于 2011-1-24 20:29 编辑 ]