http://projecteuler.net/problem=440
有一塊尺寸為1 ×n的板子。
我們想要用1 ×2的方塊和1 ×1並且上面有個位數號碼的方塊來舖滿它:
http://projecteuler.net/project/images/p440_tiles.png
例如,下列為一小部分將n = 8的板子用這些方塊舖滿的方法:
http://projecteuler.net/project/images/p440_some8.png
令T(n)為將長度為n的板子用這些方塊舖滿的方法數。
例如,T(1) = 10以及T(2) = 101。
令S(L)為Σgcd(T(c^a), T(c^b))對所有1≦a,b,c≦L得到的三重和。
例如:
S(2) = 10444
S(3) = 1292115238446807016106539989
S(4) mod 987898789 = 670616280
請求出S(2000) mod 987898789。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.154
440. GCD and Tiling