Project Euler 143

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

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

        // フェルマー点の性質より、フェルマー点とA,B,Cをそれぞれ結んだ直線は120度の角をなす。
        // よって余弦定理より、
        // p^2+pq+q^2=b^2
        // q^2+qr+r^2=a^2
        // r^2+rp+p^2=c^2
        // が成り立つ。(Eisenstein三角形?)
        // ピタゴラス数と同様、この(p,q,b)の組は生成でき、
        // 互いに素なパラメータs,t(s>t)により
        // p=(2s+t)t, q=(s-t)(s+t), b=s^2+st+t^2
        // と表される。(行列でも生成できるっぽい？)
        // 
        // p+q<=120000となる範囲で(p,q,b)の組を列挙し、
        // (p,q)を無向グラフの辺としてみて、三角形をなしていれば、
        // a,b,c,p,q,rがすべて整数という条件でのp+q+rが得られる。
        private function solve(n : uint) : Number
        {
			var lim : uint = Math.sqrt(n);
        		tr(lim); 
        		var graph : Object = {};
        		var ct : uint = 0;
        		var i : uint, j : uint, k : uint;
        		for(var s : uint = 1;s <= lim;s++){
        			for(var t : uint = 1;t < s;t++){
        				if(GCD(s, t) != 1)continue;
        				var x : uint = (2 * s + t) * t;
        				var y : uint = s * s - t * t; 
        			
	        			for(i = 1;(x + y) * i <= n;i++){
	        				var xi : uint = x * i;
	        				var yi : uint = y * i;
     	   				if(!graph[xi])graph[xi] = {};
       	 				graph[xi][yi] = yi;
        					if(!graph[yi])graph[yi] = {};
   	     				graph[yi][xi] = xi;
    	 	   				ct++;
//    	 	   				tr(xi, yi);
       	 			}
        			}
        		}
        		tr(ct);
        		
        		var set : Object = {};
        		var gct : uint = 0;
        		for(var key : String in graph){
        			var e : Object = graph[key];
        			var ctt : uint = 0;
        			for(var kk : String in e){
        				ctt++;
        			}
        			
        			if(ctt == 1)continue; // 1本しか出ていない頂点は無視
        			for each(var ei : uint in e){
        				if(int(key) >= ei)continue; // 大なり限定
        				for each(var ej : uint in graph[ei]){
	        				if(ei >= ej)continue; // 大なり限定
        					if(graph[ej][key] && ei + ej + int(key) <= n){
        						gct++;
        						var val : uint = int(key) + ei + ej;
        						set[val] = val;
//      						tr(int(key), ei, ej);
        					}
        				}
        			}
        		}
        		tr(gct);
        		
        		// 相異なるp+q+rの値を合計する
        		var sum : Number = 0;
        		for each(val in set){
        			sum += val;
        		}
        		
        		return sum;
        }

        private static function GCD(a : uint, b : uint) : uint
        { 
            while(b > 0){
                var c : uint = a;
                a = b;
                b = c % b;
            }
            return a;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}