比速度...?

google code jam每次都有3~4題 好像都存在一題非常的數學 之前看過一題 數學超強的可以O(1)

...這題低於Ｏ（ｎ）我還知道方法，Ｏ（１）.....

妳的方法是哪招啊？

用log算...就只要乘一次(羞恥的跑走)

降不行啦 會有誤差 要完全準的喔

n是整數 最大可到2000000000

可是,log3和log5的精度到小數14位耶

我又想到更羞恥的方法了

求n的因數方程式，再用迴圈把因數次方乘起來.....=口=

小數14位在n超大的時候一樣有問題 需要用數學的方式避掉浮點數精度問題。

例如, 令X (n)=(3+5^0.5)^n, Y(n)=(3-5^0.5)^n, A(n)=X (n)+Y(n), 觀察一下，這時A(n)其實就是X (n)的整數部份+1，然後把X和Y展開，我們算的就是一串整數，這樣硬算可以算出正確答案，但時間還是不行，要加上一些技巧。

然後技巧那裡我看不懂 反正還要用到矩陣相乘就對了。

題目在這 有興趣可以看看 旁邊有連結看人解出的人的code。

A(n)其實就是X (n)的整數部份+1真的太妙了

真的實在是太酷了

我也覺得想到這個很神，但更神的是有人從看完題目+想出方法+寫出程式+跑出正確結果上傳只花了20分鐘左右。

!!!!!!!!!

我終於看懂了...

還要推出這個 A(n) = 6*A(n-1) - 4*A(n-2)

到這裡可以O(n)算出A(n)

但用matrix可以把這遞迴式變矩陣的n次方，然後矩陣的n次方可以用lg(n)算完，最後就解出來了... 不知那些瞬間想出解法的人的頭腦是怎麼回事…

遞迴式變矩陣相乘算是acm中有名的技巧，最難想的還是前面的數學……囧。

......這也跟訓練有關吧，聰明加上一直不斷接觸這種機智數學的人，都會有直覺得ｆｕ，看題目一下就會聯想到可能解決的方法，那種是超人，能夠慢慢看懂得也很厲害了啊

多謝