forked from: 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/bZON
 */

// forked from uwi's Project Euler 279
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));
_N = 300;
tr(sumup120());
//            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
        {
        		_N = N;
        		return 0;
//        		return sumup90(0, 1, 1, 0) + sumup120(0, 1, 1, 0) + sumup60(0, 1, 1, 0);
        }
        
		private var _N : uint;
        
        private function sumup90(sn : int = 1, sd : int = 1, en : int = 1, ed : int = 0) : Number
        {
        		var nn : int = sn + en;
        		var nd : int = sd + ed; 
        		var c : Number = count90(nn, nd);
        		if(c == -1)return 0;
    			return c + sumup90(sn, sd, nn, nd) + sumup90(nn, nd, en, ed);
        }
        
        private function count90(n : int, d : int) : Number
    		{
        			var sup : Number = 2 * n * (n + d);
        			if(sup > _N)return -1;
        			if((n + d) % 2 == 0)return 0;
        			var xx : uint = uint(_N / sup);
        			/*
        			if(xx > 0){
        				tr(n, d, n * n - d * d, 2 * n * d, n * n + d * d);
        			}
        			*/
        			return xx;
    		}
    		
        private function sumup120(sn : int = 1, sd : int = 1, en : int = 1, ed : int = 0) : Number
        {
        		var nn : int = sn + en;
        		var nd : int = sd + ed; 
        		var c : Number = count120(nn, nd);
        		if(c == -1)return 0;
    			return c + sumup120(sn, sd, nn, nd) + sumup120(nn, nd, en, ed);
        }
        
        private function count120(n : int, d : int) : Number
    		{
        			var sup : Number = (2 * n + d) * (n + d);
        			if(sup > 3 * _N)return -1;
        			if(n / d < Math.sqrt(3))return 0;
 //        			if((n + d) % 2 == 0)return 0;
        			var xx : uint = (n - d) % 3 == 0 ? uint(_N / sup / 3) : uint(_N / sup);
        			if(xx > 0){
        				tr(n, d, 2 * n * d + d * d, n * n - d * d, n * n + n * d + d * d);
        			} 
        			return xx;
    		}
    		
        // 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;
        }
    }
}