「ルーム・アンド・ルーフ」問題
相変わらず，題名が不適切であるが。
締め切りが 2017/02/16 10:00 AM なので，その 1 分後に投稿されるように予約
設問
一辺の長さが 1 の正方形を考えます。これを P0 と呼びます。
各頂点を時計回りに A, B, C, D とします。
P0 に対し、次の手順で新しい正方形を描きます。
辺 BC と同じ辺を持つ正三角形 BCE を P0 の外側に描きます。
D と E を線分で結びます。
そして線分 DE を一辺とする正方形を右側に描きます。この正方形を P1 と呼びます。
同じ作業を P1 に対し行い、正方形 P2 を描きます。
以降同様に、P3, P4, … と次々と正方形を描くことができます。
自然数 n に対し、Pn の面積の値を小数点以下で切り捨てた値を F(n) と定義します。
例えば F(1)＝3 です。P1 の面積はおよそ 3.732 だからです。
同様に、F(2)＝13, F(3)＝51 となることが確かめられます。
標準入力から、自然数 n （1 ≦ n ≦ 10^6）が与えられます。
標準出力に F(n) を 10^6 で割った余りを出力するプログラムを書いてください。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
答えは floor((2+sqrt(3))^n) になることがすぐにわかるが，この数列は，爆発的に大きくなる。
もう一つの答えは a(n) = 4*a(n-1)+a(n-2) の漸化式があるので，こちらを使って解を求める。
R では制限時間に引っかかるので， AWK や Java で書いたら，答えが違う。
その原因は整数剰余の定義の違いだった。
R では -5 %% 6 は 1 になるが，
AWK や Java では -5 になる。
ということで，R プログラムは
f = function(n) {
a1 = 2
a2 = 4
for (i in 2:n) {
a3 = (4*a2 - a1) %% 1e6
a1 = a2
a2 = a3
}
cat(a3-1)
}
f(4) # 193
f(10) # 524173
f(601) # 868003
f(749501) # 493043
f(987654) # 378701
f(999600) # 1
AWK では，
function f(n, a1, a2, a3, i) {
a1 = 2
a2 = 4
for (i = 2; n >= i; i++) {
a3 = 4*a2 - a1
if (a3 < 0) a3 += 1e6
a3 %= 1e6
a1 = a2
a2 = a3
}
print a3-1
}
{ f($0) }
