2012-04-01から1ヶ月間の記事一覧

Project Euler 382

http://projecteuler.net/index.php?section=problems&id=382だいたいわかったが、計算がきつすぎる。高校生でもないのにこんな計算できない。

Project Euler 141(3)

Problem 141sがtで割り切れるから、 p = s / t と置きます。そうすると元の式は、 m2 = pt3(u3 + p) となります。 ここでt = 1 p = 1とすると、 m2 = u3 + 1 これは因数分解ができるので簡単に解が求められますが、こういうケースは稀なので考えません。 次…

Project Euler 141(2)

Problem 141rを平方部分とそうでない部分に分けます。例えば、24なら22と6です。一般に r = s2t(tは平方成分を含まない) と書けます。そうすると、q, dは、 q = sut d = u2t 元の式は、 n = m2 = qd + r = st(tu3 + s) ここからtはsで割り切れることを示し…

Project Euler 141(1)

Problem 141 n = m2 = qd + r とします。rはdより小さいから、r2 = qdまたはq2 = rdとなります。前者なら、 m2 = r2 + r r2と(r + 1)2の間に平方数は無いので前者はありえません。 さて、 q2 = rd が成り立つので、例えば、r = 1なら、公比は2, 3, 4, …とな…

Project Euler 137

Problem 137 AF(x) = xF1 + x2F2 + x3F3 + ... xAF(x) = x2F1 + x3F2 + x4F3 + ... x2AF(x) = x3F1 + x4F2 + x5F3 + ... 引き算して、 (1 - x - x2)AF(x) = xF1 + x2(F2 - F1) + x3(F3 - F2 - F1) + ... Fk = Fk-1 + Fk-2 F1 = F2 = 1 を使って、 (1 - x - x…

Project Euler 136

Problem 136これは前々回の面倒な方法が使えます。nが2を含まないとき、4で割って余り3の素数pなら約数は1とpですが、 y = p 4d - y = 1 なら z = p - (p + 1) / 4 > 0 で成り立ちますが、 y = 1 4d - y = p なら z = 1 - (p + 1) / 4 ≤ 0 だから成り立ちま…

Project Euler 381

http://projecteuler.net/index.php?section=problems&id=381104着、2分弱。超簡単な数論の問題。コード書くのに20分とかからなかったのに。今週か来週出題でなければ高ランク間違いなかった。せこい手を駆使したら55秒になった。ふるいの部分はO(log log n)…

Project Euler 135(2)

Problem 135難しいことを考えずに大きさNのリストaを用意して、 y(4d - y) = n のyと4d - yを振ってその結果得られたnに対し、 a[n] += 1 とすればよいです。 0.8sでした。こんな実質10行に満たない単純な方法の方が速いんですね。

Project Euler 135(1)

Problem 135公差をdとすると、x = y + d, z = y - dだから、 x2 - y2 - z2 = -y2 + 4dy = y(4d - y) = n nを素因数分解して約数を生成します。その約数をd1としてd2 = n / d1とすると、 y = d1 4d - y = d2 4d = d1 + d2 だから、d1 + d2が4で割り切れてd1が…

Project Euler 131

Problem 131 n3 + n2p = m3 とおきます。ここで、nがpの倍数と仮定しましょう。n = kpとすると、 p3 + p = (m/k)3 p3と(p + 1)3の間に立方数はないので矛盾。よってnとpは互いに素です。 さて、nは立方数です。なぜなら、nに立方数でない因子があるとすると…

Project Euler 380

http://projecteuler.net/index.php?section=problems&id=38045着。4時間以上かかった。 しかし、ポイントだけ考えればこれでも十分。このままいけば9ポイントくらいつく。 問題の特性を考慮して修正したら、Pythonで160s、C++で0.7sになった。O(W3H)になっ…

Project Euler 133

Problem 1335より大きい素数pに対し、A(p)が2と5のみから成り立っていなければなりません。そこで、p - 1から2と5を取り出して、例えばp = 73ならp - 1 = 23 * 32だから23 = 8ですが、 108 ≡ 1(mod 73) なので、A(p)は8の約数で、十分に大きな10nを割り切る…

Project Euler 132

Problem 1322, 3, 5以外の素数を列挙します。A(p)(すなわちB(p))が109を割り切る素数pを列挙すればよいです。109を割り切るかどうかの判定は比較的簡単です。まず、p - 1の2と5の成分を取り出します。例えばp = 1920001として、p - 1 = 210 * 3 * 54だから…

Project Euler 130

Problem 130前回の定義でB(n)は、 10e ≡ 1(mod n) を満たす最小のe(> 0)としました。これをnの既約剰余類群での10の位数と言います。これを効率的に求めればよいです。nを素因数分解して、 n = p1e1...pmem とすると、 B(n) = lcm(B(p1e1), ... , B(pmem)) …

Project Euler 129

Problem 129A(n)は、 (10e - 1) / 9 ≡ 0 (mod n) となる1以上で最小のeです。 nが2または5で割り切れるとき、この式を満たすeは無いので考慮に入れません。 A(n)は、nが3で割り切れないとき、 10e ≡ 1 (mod n) となる最小のeです。7の剰余なら、10から10倍し…

Project Euler 379(3)

http://projecteuler.net/index.php?section=problems&id=379ちょっと工夫したら28分になった。 久しぶりに20着以内だったので、ランキングを見てみたら25位だった。従来のPositionだけじゃなく、Speedという要素も追加されていた。しかし、これは実態に合っ…

Project Euler 379(2)

http://projecteuler.net/index.php?section=problems&id=37917着。1時間以上かかった。

Project Euler 379(1)

http://projecteuler.net/index.php?section=problems&id=379かつてないほどつながるのに時間がかかった。 問題についてはほとんど考えていない。

Project Euler 127

Problem 127 9秒でした。

Project Euler 124(2)

Problem 124もっと速い方法を考えましょう。10万で9ms、1000万で1.1sでした。

Project Euler 124(1)

Problem 124何の工夫もしていませんが、0.4sです。

Project Euler 378

http://projecteuler.net/index.php?section=problems&id=37834着。13分。速くなりそうな気がしない。