Project Euler 202

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

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

        // N=12017639147とする。
        // 正三角形を折り返していくと、
        // N回反射で到達する点はすべて同一直線上にあることがわかる。
        // #{(x,y)|x>0, y>0 かつ x+y=M かつ x-y=0(mod 3) かつ GCD(x,y)=1}
        // の値を求めればよい。ただしM=(N+3)/2=6008819575.
        // M=1(mod 3)なので、x=y=2(mod 3). x=3m+2, y=3n+2とおくと、
        // GCD(x,y)=GCD(M,y)=GCD(M,x-y)=GCD(M,m-n)
        // さらにM,m-nは奇数なので、m-n=2t+1として
        // GCD(M,m-n)=GCD(M,(M-(2t+1))/2)
        // これで、求める値は、
        // #{t|t=(M+2)/3,･･･,(M-1)/2 かつ GCD(M,t)=1}*2
        // となる。M=5*5*11*17*23*29*41*47と、異なる素因数の種類数が少ないため、
        // 上記の値は、Mの各約数?から求められる。
        //
        // N=1000001の場合は、Mが偶数になるので、m-n=4tとして、
        // GCD(M,m-n)=GCD(M,t)から
        // #{t|t=1,･･･,(M-4)/12 かつ GCD(M,t)=1}*2
        private function solve(N : Number) : Number
        {
            var M : Number = (N + 3) / 2;
            var ret : Number = countCoPrimes(M, (M + 2) / 3, (M - 1) / 2) * 2;
//            var ret : Number = countCoPrimes(M/2, 1, int((M - 4) / 12)) * 2;
            return ret;
        }
        
        private function countCoPrimes(N : Number, a : Number, b : Number) : Number
        {
            var n : Number = N;
            var sq : int = Math.sqrt(n);
            var pfs : Array = [];
            for(var i : int = 2;i <= sq;i++){
                if(n / i == Math.floor(n / i)){
                    pfs.push(i);
                    while(n / i == Math.floor(n / i))n /= i;
                    sq = Math.sqrt(n);
                }
            }
            if(n > 1)pfs.push(n);
            
            tr(pfs);
            var sum : Number = 0;
            for(var c : int = 1;c < 1 << pfs.length;c++){
                var d : int = 1;
                var l : int = 0;
                for(var j : int = c, k : int = 0;j > 0;j >>= 1, k++){
                    if((j & 1) == 1){
                        d *= pfs[k];
                        l++;
                    }
                }
                sum += ((l & 1) == 1 ? 1 : -1) * (int(b / d) - int((a - 1) / d));
            }
            return (b - a + 1) - sum;
        }

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