Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

2010-04-27

Project Euler #73

| 01:37 | Project Euler #73 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #73 - nitoyon.dispatchEvent(null)

nとdを正の整数として, 分数 n/d を考えよう. n<dかつHCF(n,d)=1のとき, 真既約分数と呼ぶ.</ppp>

d ≤ 8について既約分数を大きさ順に並べると, 以下を得る:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

1/3と1/2の間には3つの分数が存在することが分かる.

では, d ≤ 12,000 について真既約分数をソートした集合では, 1/3 と 1/2 の間に何個の分数があるか?

Problem 73 - PukiWiki

先日解いた #71 とほぼ同じロジック。真既約かどうかは調べなきゃ分からないので、d を固定した上で 1/2 から 1/3 の範囲の真既約分数を列挙していく。

ちょっと計算時間はかかるが、しばらくすれば正しい答えが出てくる。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem73 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const D:int = 12000;

    public function Problem73(){
        var n:int = 1, d:int = 3;
        var count:Number = 0;
        setTimeout(function():void {
            for (var i:int = 0; i < 100; i++) {
                if (d > D) {
                    t.text = count + "";
                    return;
                }

                n = d / 3;
                while (true) {
                    if (n / d > 1 / 3) {
	                    if (n / d >= 0.5) break;
	                    if (gcm(n, d) == 1) count++;
					}
                    n++;
                }

                d++;
            }

            t.text = "checking " + n + "/" + d;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function gcm(a:int, b:int):int {
        if (a < b) return gcm(b, a);
        if (a % b == 0) return b;
        return b > a - b ? gcm(b, a - b) : gcm(a - b, b);
    }
}
}