メモ化の威力に感動した。 Problem 76 - PukiWiki 100の和の組合せを求める。両替問題のヤバいバージョン。 ナイーブにやってみたら50で破綻した。 1だけの組合せになったら1種類と特殊化することで40秒で完了できるようになった。 同じ計算を何度もやってる…

久しぶりにキマッた。 Problem 69 - Project Euler翻訳無かったけど、オイラーの関数に関する問題。 オイラーの関数φ(n)は、nと互いに素な整数の個数を表す。例えば、φ(6) = {1,5} = 2 φ(10) = {1,3,7,9} = 4n/φ(n)とすれば、nのなかに互いに素な整数の割合…

もうちょいいこう。Problem 71 - PukiWiki100万以下の真既約分数を小さい順に並べて、3/7の左側に来る分数の分子を答える。 素直に並べたら、100万の2乗回はかかるのでムリっぽい。んじゃ、と思って3/7以下に絞ってみたけど、1000分割位で破綻。100万 * 40万…

落ち着いて範囲を考える。 Problem 63 - PukiWiki n乗してn桁になる数はいくつあるか。 ふむふむ。適当に計算してみる。 まず終端。10^1は2桁,10^2は3桁,10^3は4桁・・・となるので、10^nはn乗するとn+1桁。絶対に追いつかない。10以上は除外できる。 小さい…

回文数絡み。 Problem 55 - PukiWiki 349を反転させて足していくと349 + 943 = 1292,1292 + 2921 = 4213,4213 + 3124 = 7337回文数になるらしい。不思議だ。回文数にならないものをLychrel数と言うらしい。50回回しても回文数が見つからなければ、Lychrel数…