Project Euler 279

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

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

        // 三角形の頂角をθとすると、辺の長さがすべて整数なので
        // 余弦定理より、cosθは有理数になる。
        // cosθが有理数になるのは、θ=60°, 90°, 120°だけ？？
        // なので、
        // x^2+y^2=z^2
        // x^2+xy+y^2=z^2
        // x^2-xy+y^2=z^2
        // のどれかを満たし、
        // x+y+z<=Nであるものの個数を列挙すればよい。
        // これは他の問題にもよく出てくるので、まとめとしてちょうどいい。
        // 行列生成のやつもできればしたいなぁ
        private function solve(N : uint) : Number
        {
        		return countPythagoras(N) + countEisenstein120(N) + countEisenstein60(N);
        }
        
        private function countPythagoras(N : uint) : Number
        {
        		var u : uint, v : uint;
        		// (u^2-v^2, 2uv, u^2+v^2)
        		// (u^2-v^2+2uv+u^2+v^2=2u(u+v) <= N)
        		var ulim : uint = Math.sqrt(N/2);
        		var ct : Number = 0;
        		for(u = 1;u <= ulim;u++){
        			for(v = 1+(u&1);v < u;v+=2){
        				if(GCD(u, v) > 1)continue;
//        				tr(u,v,u*u-v*v,2*u*v);
        				var perimeter : uint = 2 * u * (u + v);
        				ct += uint(N / perimeter);
        			}
        		}
        		return ct;
        }

        // 1角が120度の整数辺長の三角形を列挙
        private function countEisenstein120(N : uint) : Number
        {
        		var u : uint, v : uint;
        		// (2uv+v^2,u^2-v^2,u^2+uv+v^2)
        		// (sum=2u^2+3uv+v^2=(2u+v)(u+v) <= N)
        		var ulim : uint = Math.sqrt(N/2);
        		var ct : Number = 0;
        		var div : Number = Math.sqrt(3) + 1;
        		for(u = 1;u <= ulim;u++){
        			for(v = 1;v <= u/div;v++){
        				if((u - v) % 3 == 0)continue;
        				if(GCD(u, v) > 1)continue;
        				var perimeter : uint = (2*u+v)*(u+v);
//        				tr(u,v,2*u*v+v*v,u*u-v*v,u*u+u*v+v*v, perimeter); 
        				ct += uint(N / perimeter);
        			}
        		}
        		// u-vが3の倍数のとき用
        		var ulim3 : Number = Math.sqrt(3) * ulim + 1;
        		for(u = 1;u <= ulim3;u++){
        			for(v = u%3;v < u/div;v+=3){
        				if(GCD(u, v) > 1)continue;
        				perimeter = (2*u+v)*(u+v)/3;
 //       				tr(u,v,2*u*v+v*v,u*u-v*v,u*u+u*v+v*v,perimeter);
        				ct += uint(N / perimeter);
        			}
        		}
        		return ct;
        }

        // 1角が60度の整数辺長の三角形を列挙
        private function countEisenstein60(N : uint) : Number
        {
        		var u : uint, v : int;
        		// (2uv-v^2,u^2-v^2,u^2-uv+v^2)
        		// (sum=2u^2+uv-v^2=(2u-v)(u+v) <= N)
        		var ulim : uint = Math.sqrt(N/2);
        		var ct : Number = 0;
        		for(u = 1;u <= ulim;u++){
        			for(v = 1;v <= u/2;v++){
        				if((u + v) % 3 == 0)continue;
        				if(GCD(u, v) > 1)continue;
        				var perimeter : uint = (2*u-v)*(u+v);
//        				tr(u,v,2*u*v-v*v,u*u-v*v,u*u-u*v+v*v); 
        				ct += uint(N / perimeter);
        			}
        		}
        		// u+vが3の倍数のとき用
        		var ulim3 : Number = Math.sqrt(3) * ulim + 1;
        		for(u = 1;u <= ulim3;u++){
        			for(v = 3 - (u%3);v <= u/2;v+=3){
        				if(GCD(u, v) > 1)continue;
        				perimeter = (2*u-v)*(u+v)/3;
//        				tr(u,v,2*u*v-v*v,u*u-v*v,u*u-u*v+v*v,perimeter); 
        				ct += uint(N / perimeter);
        			}
        		}
        		return ct;
        }
        
        private function test(N : uint) : Number
        {
        		var ct : uint = 0;
        		var cache : Object = {};
        		for(var a : uint = 1;a <= N;a++){
        			for(var b : uint = 1;b <= N;b++){
        				for(var c : uint = 1;c <= N;c++){
        					if(a + b + c > N)break;
        					var xx : Number = (a * a + b * b - c * c) / (2 * a * b)
        					if(xx == 0 || xx == 0.5 || xx == -0.5){
//        					if(xx == 0.5){
        						var ar : Array = [a, b, c];
        						ar.sort();
        						var code : uint = ar[0] * N * N + ar[1] * N + ar[2];
        						if(cache[code])continue;
//        						if(a != b && a != c)tr(a, b, c, xx);
        						cache[code] = 1;
        						ct++;
        					}
        				}
        			}
        		}
        		return ct;
        }

        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;
        }
    }
}