2010-07-01から1ヶ月間の記事一覧

Project Euler 140

http://projecteuler.net/index.php?section=problems&id=140 Problem 137と同じように見えますが、より難しくなっています。 同じように計算していくと、 (n + 3)x2 + (n + 1)x - n = 0 xが有理数になる必要十分条件は判別式が平方数になることだから、 5n2…

NULLでハマった

例えば、multimapで同じキーを持つ要素の個数を調べたいとしましょう。 #include <iostream> #include <map> #include <algorithm> #include <functional> using namespace std; struct S { }; int main() { multimap<int,S *> m; for(int n = 0; n < 3; n++) { m.insert(make_pair(1, new S())); m.insert(m</int,s></functional></algorithm></map></iostream>…

Project Euler 139

http://projecteuler.net/index.php?section=problems&id=139 単にピタゴラス数で条件に合う組合せを数えても1分くらいでした。 from itertools import * from fractions import gcd def gen_primitive_Pythagorean(L): for m in takewhile(lambda m: m * (2…

Project Euler 138

http://projecteuler.net/index.php?section=problems&id=138 (b / 2, h, L)でピタゴラス数で、hが偶数だとhとbの差が偶数になってしまうので、 h = m2 - n2 b = 4mn L = m2 + n2 m2 - n2 - 4mn = ±1 (m - 2n)2 - 5n2 = ±1 これもペル方程式です。

Project Euler 137

http://projecteuler.net/index.php?section=problems&id=137 Fk = Fk-1 + Fk-2 を利用すれば簡単です。 AF(x) + xAF(x) = xF1 + x2(F2 + F1) + x3(F3 + F2) + ... = xF2 + x2F3 + ... = (AF(x) - x) / x AF(x) = x / (1 - x - x2) これがnだとすると、 n x2…

Project Euler 136

http://projecteuler.net/index.php?section=problems&id=136 前問と同じ方法では時間がかかりすぎます。前問では全体を同時に計算しましたが、これで遅いときは逆に個々に計算するとよいことがあります。ここでは解の個数が1になる条件を考えます。 n = (3d…

mem_funの使い方

例えばfor_eachの第3引数ですが、ここは関数オブジェクトを指定します。しかしそれを一々作るのもどうかと思うので、関数があればptr_funで関数オブジェクトを作ってそれを利用します。 #include <iostream> #include <vector> #include <algorithm> using namespace std; void print(int </algorithm></vector></iostream>…

Project Euler 135

http://projecteuler.net/index.php?section=problems&id=135 初項をa、公差をdとすると、 n = (a + 2d)2 - (a + d)2 - a2 = (3d - a)(d + a) となります。 dを固定してaを変えましょう。dが小さいとき、1 ≤ a ≤ 3d - 1となりますが、dが大きいときにa = dを…

Project Euler 134

http://projecteuler.net/index.php?section=problems&id=134 p1 = 19、p2 = 23とすると、 100x + p1 = p2y という不定方程式を解くだけです。 Pythonにはteeという関数があるのですね。 from itertools import tee def gen(): for n in xrange(10): print n…

Project Euler 133

http://projecteuler.net/index.php?section=problems&id=133 素数pでR(10n)が割り切れるということは、A(p)でR(10n)が割り切れるということです。そのようなnが存在するということは、A(p)は2か5以外の因子を含まないということです。

Project Euler 132

http://projecteuler.net/index.php?section=problems&id=132 この問題は、素直に10のべき乗の素数による剰余を計算すればよいでしょう。

それでも2倍だ

http://www.kmonos.net/wlog/111.html#_1001100720 かなり遅れた反応だったにもかかわらず(書く時間がなかなか取れなかった)、うちの記事を取り上げていただきました。ありがとうございます。 例えば、32bit整数を1億個のvectorを構築して、それに1個加え…

Project Euler 131

http://projecteuler.net/index.php?section=problems&id=131 n3 + n2p = r3 と書けます。 まず、nが因子pをe個含むとしましょう。 n = pe m n3 + p n2 = p2e+1(pe-1m + 1)m2 最初の項以外はpを含まないので2e+1は3で割り切れます。そうすると、e-1も3で割り…

Project Euler 130

http://projecteuler.net/index.php?section=problems&id=130 前回の方法でも十分速く答えが出ますが、もっと速い方法があります。前回は小さい長さのrepunitから一つずつ順に割り切れるかどうか調べました。しかし実際には全てを調べる必要はありません。 …

本当に1.5倍のほうがメモリ効率がよいのか

C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 2倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域…

Project Euler 129

http://projecteuler.net/index.php?section=problems&id=129 1が続く数は、1からはじまって10倍して1を足すを繰り返します。そのnの剰余を計算するとき、最初に1が続く数を作るととてつもなく大きな数になってしまいます。そこで10倍して1を足してからnの剰…

Project Euler 128

http://projecteuler.net/index.php?section=problems&id=128 素直に回って座標を出します。ここでは、1を原点、2を(1, 0)、3を(0, 1)とする空間(平面)で考えます。今考えている座標より1層多く計算している素数の個数を計算できるので、1層分早いのと2つ…

Project Euler 127

http://projecteuler.net/index.php?section=problems&id=127 a = 1の場合は簡単です。その他の場合を考えましょう。 例えばcが16とすると、c / rad(c) = 8となります。だから、rad(a) * rad(b) aとbはそれぞれ2以外の因子を持たなければなりません。2以外で…

Project Euler 126

http://projecteuler.net/index.php?section=problems&id=126 まず、a × b × cでm層目の立方体の数は、詳しくは書きませんが、サイドとそれ以外を分けて考えると易しいです。 P ≡ a + b + c Q ≡ b c + c a + a b とすると、 Am = 4(m-1)(P+m-2) + 2Q となり…

Project Euler 125

http://projecteuler.net/index.php?section=problems&id=125 2乗和の公式を使えば、 m2 + … + n2 = n(n+1)(2n+1) / 6 - (m-1)m(2m-1) / 6 あとは回文数の判定をするだけです。

Project Euler 124

http://projecteuler.net/index.php?section=problems&id=124 10万より小さい自然数を素因数分解し、radを計算してソートするだけです。 もう少し速い方法はないでしょうか。まず、べき乗を含まない自然数を出します。10までなら2,3,5,6,7,10です。例えばrad…

Project Euler 123

http://projecteuler.net/index.php?section=problems&id=123 (pn-1)n + (pn+1)n = 2n pn (n : 奇数) (pn-1)n + (pn+1)n = 2 (n : 偶数) なので、あとは素数を小さいものから順に出すだけです。上限が決まっていないので、エラトステネスのふるいを少しずつ…

Project Euler 122

http://projecteuler.net/index.php?section=problems&id=122 べき乗の計算はいわゆるバイナリ法を使うと速いですが、実はバイナリ法より乗算の回数が少ない方法があるという話です。 例えば5乗なら、 a -> a2 -> a4 -> a5 a -> a2 -> a3 -> a5 a -> a2 -> a…

Project Euler 121

http://projecteuler.net/index.php?section=problems&id=121 4回の場合、全体の場合の数は2*3*4*5、4勝する場合の数は1*1*1*1、3勝する場合の数は1回目に負ける場合の数は1*1*1*1、2回目なら1*2*1*1、3回目1*1*3*1、4回目1*1*1*4なので、勝つ確率は11/120と…

Summer Break

PE

次の出題時間が出ないのでニュースを見たら、夏休みだそうだ。 Problem 300は9月。

Project Euler 120

http://projecteuler.net/index.php?section=problems&id=120 (a-1)n + (a+1)nのa2の剰余は、nが奇数なら 2an 偶数なら 2 だから、nが奇数なら rmax = a(a-1) 偶数なら rmax = a(a - 2) となります。

Project Euler 119

http://projecteuler.net/index.php?section=problems&id=119 調べる範囲を狭めることができます。例えば2乗のとき、3桁の2乗は6桁以下だから各桁を足しても54以下です。2桁なら2乗して4桁以下で各桁を足して36以下だから、底が36より大きいことはありません…

Project Euler 118

http://projecteuler.net/index.php?section=problems&id=118 これも再帰に持ち込めます。[1,2,3,4,5,6,7,8,9]を用意して、ここから数字をいくつか取り出します。重複を避けるために最も左の数字は必ず選びます。例えば1と3を選んだとき、13も31素数なので、…

Project Euler 117

http://projecteuler.net/index.php?section=problems&id=117 漸化式にすれば一発です。この問題が最も単純でした。

Project Euler 116

http://projecteuler.net/index.php?section=problems&id=116 これもProblem 114と同じですね。最後に全て1を除く処理をしています。