作者LPH66 (-858993460)
看板Prob_Solve
標題Re: [問題] Google Code Jam 2008, Round 1A - C
時間Thu Mar 8 10:20:04 2012
令 x = 3 + √5 y = 3 - √5
易知 x+y = 6 xy = 4 (這是 y 選這個值的原因之一)
那麼 x^2 + y^2 = (x+y)^2 - 2xy = 36 - 8 = 28
x^3 + y^3 = (x+y)(x^2+y^2) - xy(x+y) = 6(28) - 4(6) = 144
x^4 + y^4 = (x+y)(x^3+y^3) - xy(x^2+y^2) = 6(144) - 4(28) = 752
等等
一般來說我們有 x^n + y^n = (x^(n-1) + y^(n-1))(x+y) - (x^(n-2)+y^(n-2))(xy)
若令 A_n = x^n + y^n 則我們就有
A_0 = 2 A_1 = 6 A_n = 6A_(n-1) - 4A_(n-2) 這樣的遞迴式
而所求的 floor(x^n) 即為 (A_n) - 1
(這是由於 0 < y < 1 所以 0 < y^n < 1, 這是 y 選這個值的原因之二)
由於有這樣的遞迴式的關係 一定時間之後必然會發生循環
最最粗略的估計 觀察到除了前兩項外後面的所有項都是四的倍數
(A_2 = 28, 因此 A_3 之後全部都是四的倍數)
因此前兩項的末三位到後來至多只會有 250^2 = 62500 種組合
於是在 62500 項後必定存在循環
基本上這樣就足夠寫出一個不慢的程式了
而且實際上如你所發現的 其實一百項之後就循環了 XD
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.62
→ stimim:如果這一題改為 (4+sqrt(5))^n 有要怎麼算呢? 03/08 10:39
推 RockLee:感謝L大的開示, 我原本的algorithm還真的去算sqrt Orz... 03/08 13:28
→ RockLee:還好這題100項就發生循環 03/08 13:29
→ RockLee:如果62500項才發生循環就看不出來了 XD 03/08 13:30
→ RockLee:不過我也很好奇若是 (4+sqrt(5))^n 的話怎麼算? 03/08 13:30
推 Leon:nice solution! 03/08 13:57
→ stimim:cool! 03/08 19:33