Project Euler 184

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

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

        // 三角形のうち2頂点A,Bを選べば、
        // 原点を含むような三角形をつくるための3頂点目Cの組み合わせは、
        // 対称性よりA,Bの間にある点の個数になる。
        // また、原点からみてA,Bのある方向にCはこない。
        // 第1象限+x軸正上にある格子点の個数をNとすると、
        // 原点からみて格子点の重複がないときの三角形の個数は
        // (0+1+...+(2N-2))*4N/3 (B,Cの選び方)*(Aの選び方)/(三角形の重複)
        // ((2N-1)(2N-2)/2)*4N/3
        // r=2の場合は重複がないのでこれで求められる。
        // AがM個重複している場合、(B,Cの選び方)は、
        // (2N-M)(2N-(M+1))/2
        // となる。BのなかにK個の重複項が含まれていれば、ここから
        // K(K-1)/2ひけばよい。
        // この値はBの位置に関係ないので、
        // 全体でのK(K-1)/2の和=Sを求めてから、M(M-1)/2分ひいたものを
        // 使えば良い。
        // よってφ(M)を原点からみてM個重複している点列の総数とすると、
        // Σ_M [M*φ(M)*((2N-M)(2N-(M+1))/2-(S-M(M-1)/2))/3]
        // が答え。ただし、
        // S=Σ_K [φ(K)*K(K-1)/2].
        private function solve(r : uint) : Number
        {
        		var p : Vector.<Vector.<uint>> = new Vector.<Vector.<uint>>(r);
        		var i : uint, j : uint, k : uint;
        		for(i = 0;i < r;i++){
        			p[i] = new Vector.<uint>(r);
        			for(j = 0;j < r;j++)p[i][j] = 0;
        		}
        		
			var c : Array = new Array(r);
			for(i = 0;i < c.length;i++)c[i] = 0;
			
			var gct : uint = 0;
			var ggct : uint = 0;
        		// i : y, j : x;
        		for(i = 1;i < r;i++){
        			for(j = 0;j < r;j++){
        				if(p[i][j] == 1 || i * i + j * j >= r * r)continue;
        				for(k = 1;(i * i + j * j) * k * k < r * r;k++){
        					p[i*k][j*k] = 1;
        				}
        				k--;
        				c[k]++;
        				gct += k;
        				ggct += (k - 1) * k / 2;
        			}
        		}
        		tr(c);
        		tr(gct, ggct);
        		
        		var sum : Number = 0;
        		for(i = 1;i < r;i++){
        			if(c[i] == 0)continue;
        			var d : Number = ((2 * gct - i) * (2 * gct - (i + 1)) / 2 - (2 * ggct - (i - 1) * i / 2)) * 4 * c[i] * i;
        			tr(i, d);
        			sum += d;
        		}
        		return sum / 3;
        }
		
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}