Project Euler 139

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/eHHF
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=139
    public class Euler139 extends Sprite {
        private var _tf : TextField;
  
        public function Euler139() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve(100000000));
            var g : int = getTimer();
            t((g - s) + " ms");
        }

        // ピタゴラス数を生成する。
        // 自然数m>n ((m,n)=1, m,nいずれか偶数)について
        // a=m^2-n^2, b=2mn, c=m^2+n^2とする。
        // (a-b)|cかつa+b+c<100000000となればよい。(ka,kb,kc)についても成り立つので、
        // 条件を満たすa,b,cから、|(100000000-1)/(a+b+c)|を求めればよい。
        //
        // (a-b)|cのとき、a-b=±1を示す。
        // (|a-b|,c)=1が示せれば、(a-b)|cよりa-b=±1なので、(|a-b|,c)=1を示す。
        // (|a-b|,c)=(|m^2-n^2-2mn|,m^2+n^2)
        //          =(|m^2-n^2-2mn|,2n(n+m)) (第2項にm^2-n^2-2mnを減じた)
        // ここで、(|m^2-n^2-2mn|,n)=(m^2,n). (m,n)=1より(m^2,n)=1
        // また、(|m^2-n^2-2mn|,n+m)=(2mn,n+m)=(mn,n+m)=(m^2,n+m).
        // (m,n)=1より、(m,n+m)=1. ゆえに(m^2,n+m)=1.
        // また、|m^2-n^2-2mn|は奇数なので(|m^2-n^2-2mn|,2)=1.
        // 以上より(|m^2-n^2-2mn|,2n(n+m))=1なのでOK.
        // 
        // a-b=±1より、m^2-n^2-2mn=±1. mについて解いて
        // m=n+√(2n^2±1)
        // nをインクリメントしていって√(2n^2±1)が整数かつ条件を満たすmが存在するとき、
        // (a-b)|cをみたす(a,b,c)が求まる。
        // 
        // nの上限は、100000000>a+b+c=2m(m+n)>2(1+√2)(2+√2)n^2より、
        // n<√(100000000/2(4+3√2)) (およそ2463)
        private function solve(M : int) : int
        {
            var ret : int = 0;
            var ccc : Number = Math.sqrt(M / 2 / (4 + 3 * Math.sqrt(2)));
            for(var n : int = 1;n <= ccc;n++){
                var sqn : Number = Math.sqrt(2 * n * n + ((n & 1) == 0 ? 1 : -1));
                if(int(sqn) != sqn)continue;
                var m : Number = n + sqn;
                if(((m ^ n) & 1) == 0 || GCD(m, n) > 1)continue;
                
                var a : Number = m * m - n * n;
                var b : Number = 2 * m * n;
                var c : Number = m * m + n * n;
                var s : Number = Math.abs(b - a);
                if(c % s == 0){
                   t(a + "\t" + b + "\t" + c);
                   ret += int((M - 1) / (a + b + c)); 
                }
            }
            return ret;
        }
        
        private static function GCD(a : int, b : int) : int
        {
            return b == 0 ? a : GCD(b, a % b);
        }

	private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}