作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 440 GCD and Tiling
时间Tue Oct 15 14:17:55 2013
440. GCD and Tiling
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