Project Euler

■162
[桁数][0,1,Aの各々を1つ以上含んでいるか]でDP．
初期値は以下．
dp[1][1<<1]=1…1桁で1を含む
dp[1][1<<2]=1…1桁でAを含む
dp[1][0]=13…1桁で0,1,Aを除いた13個
最下位に0,1,…E,Fを付加していく形の更新式を作る．
dp[桁数][(1<<3)-1]が答え．
オーバーフローするので，BigIntegerで手抜きした．

■075
ピタゴラス数生成行列を使用．↓参照．
http://www.sci.hyogo-u.ac.jp/matsuyam/undergrad/gakubu07.htm
これを使うと，原始的ピタゴラス数p=[a,b,c]^tから，3つの原始的ピタゴラス数q_k=1,2,3=[a_k,b_k,c_k]^tを生成出来る．また，a+b+c<a_k+b_k+c_kであることは容易に分かる．よって，a+b+c>Lとなるpで枝刈りを行うBFSをすれば良い．

■204
やるだけ．100未満の素数を先に生成し，そこから重複無く効率良く値を計算していく．

■100
青の円盤の枚数をa，赤の円盤の枚数をbとすると，
a/(a+b) * (a-1)/(a+b-1) = 1/2
が成り立つ．
これをaについて解くと，
a=[2b+1±√(8b²+1)]/2
となる．
2b+1<√(8b²+1)
かつ，
a>0であるため，
a=[2b+1+√(8b²+1)]/2
と一意に定まる．
aは自然数であるため，判別式の値8b²+1は平方数で無くてはならない．
8b²+1=k²
とし，これを整理すると，
k²-8b²=1
という形のペル方程式になる．
この最小解は，問題文より，b=1の時であるため，
k=3であると容易に分かる．

ペル方程式について以下が成り立つ．
x-Dy²=±1
について自明でない最小解を(x, y)とする．
α=x+√Dy
に対して，
αⁿ=x_n+√Dy_n
とすると，(x_n, y_n)もまた上記方程式の解となる．

このため，α=3+√8とおき，
αⁿ=k_n+b_n√8
を計算し，そこからa_nを算出．
aⁿ+bⁿ>10¹²となれば終了．そうでなければ，nを1ずつ増加させていく．