Project Euler 277

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=277
    public class Euler277 extends Sprite {
        private var _tf : TextField;
  
        public function Euler277() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve("UDDDUdddDDUDDddDdDddDDUDDdUUDd", 1E15));
//            tr(solve("DdDddUUdDD", 1E6));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var CMAP : Object = {
        		"D" : [0, 1],
        		"U" : [-2, 4],
        		"d" : [1, 2]
        };

        // 最終的な数をxとすると、逆操作によって、
        // D -> 3x, U -> (3x-2)/4, d -> (3x+1)/2
        // という風に変換されていく。そして最初に戻ったとき、
        // その数(a_1)が整数でありかつ10^15をこえていればよい。
        // seqの文字数をLとする。
        // 
        // 変換途中の数は(3^k*x+a)/b の形で表されることに注意して、最終的なa,bを求める。
        // 最初の数は(3^L*x+a)/b で表される。
        // これが整数となるためには、x=-a*3^-L (mod b)となればよい。
        // こうしてxが求まれば、求める値(a_1)は
        // (3^L*(Ab+x)+a)/bの形で表されるので、
        // あとは、わかるな？
        private function solve(seq : String, min : Number) : Number
        {
        		var a : Number = 0, b : Number = 1;
        		var L : uint = seq.length;
        		var i : int, j : int;
        		for(i = L - 1;i >= 0;i--){
        			var c : Array = CMAP[seq.charAt(i)];
        			if(c == null)return -i-1;
        			var na : Number = a * 3 + b * c[0];
        			var nb : Number = b * c[1];
        			a = na;
        			b = nb;
        		}
        		tr(a, b, a % b);
        		var x : Number = -(a%b) * exmod(3, b/2-L, b);
        		x %= b;
        		if(x < 0)x += b;
        		tr(x);
        		
        		var minp : Number = (min * b - a) / Math.pow(3, L);
        		var u : uint = Math.ceil((minp - x) / b);
        		var minx : Number = x + u * b;
        		tr(minx);
        		return (Math.pow(3, L) * minx + a) / b;
        }
        
        // a^n(mod p)
        private function exmod(a : uint, n : uint, p : uint) : uint
        {
            var mul : Number = a;
            var ret : Number = 1;
            for(var i : uint = n;i > 0;i >>= 1){
                if((i & 1) == 1){
                    ret *= mul;
                    ret %= p;
                }
                mul *= mul;
                mul %= p;
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}