Project Euler 157

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

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

        // 1/a+1/b=p/10^n より (a+b)*10^n/ab=p つまり
        // ab | (a+b)*10^n であればよい。
        // GCD(a,b)=1のとき、GCD(a+b,ab)=1なので
        // abは10^nの約数になる。これを満たす(a,b)をまず列挙しておく。
        // GCD(a,b)=gのとき、a'=a/g, b'=b/gとすると
        // GCD(a',b')=1, (a+b)/ab=(a'+b')/a'b'g となるので、
        // a'b'gは10^n*(a'+b')の約数になる。(a',b')を固定すると、
        // gは、10^n*(a'+b')/a'b'の約数なので、
        // 先に列挙した(a,b)の上でgの個数を数えるようにすればよい。
        private function solve(N : int) : int
        {
            var f : Object;
            var num : int, v : int;
            var pa : int, pb : int, a : int, b : int;
            
            var ret : int = 0;
            for(var n : int = 1;n <= N;n++){
                var sum : int = 0;
                
                // GCD(a,b)=1
                // (a, b) = (2^pa, 5^pb) (pa, pb >= 0)
                for(pa = 0, a = 1;pa <= n;pa++, a *= 2){
                    for(pb = 0, b = 1;pb <= n;pb++, b *= 5){
                        // 素因数分解して、a,bで吸収されなかった分の10^nの素因数を足す
                        f = factor(a + b);
                        if(!f[2])f[2] = 0;
                        if(!f[5])f[5] = 0;
                        f[2] += n - pa;
                        f[5] += n - pb;
                        
                        // gの個数を数える
                        num = 1;
                        for each(v in f){
                            num *= (v + 1);
                        }
//                        tr(a, b, num);
                        sum += num;
                    }
                }
                
                // (a, b) = (1, 2^pa * 5^pb) (pa, pb >= 1)
                for(pa = 1, a = 2;pa <= n;pa++, a *= 2){
                    for(pb = 1, b = 5;pb <= n;pb++, b *= 5){
                        f = factor(1 + a * b);
                        if(!f[2])f[2] = 0;
                        if(!f[5])f[5] = 0;
                        f[2] += n - pa;
                        f[5] += n - pb;
                        
                        num = 1;
                        for each(v in f){
                            num *= (v + 1);
                        }
//                        tr(a, b, num);
                        sum += num;
                    }
                }
                
                tr(n, sum);
                ret += sum;
            }
            
            return ret;
        }
        
        private function factor(n : int) : Object
        {
            var ret : Object = {};
            var sq : int = Math.sqrt(n);
            for(var i : int = 2;i <= sq;i++){
                var ct : int = 0;
                while(n % i == 0){
                    n /= i;
                    ct++;
                }
                if(ct > 0){
                    ret[i] = ct;
                    sq = Math.sqrt(n);
                }
            }
            if(n != 1){
                ret[n] = 1;
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}