Project Euler 156

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

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

        // f(n,d)=1~nで登場するdの個数とする。
        // s(d)=(f(n,d)=nを満たすnの総和) とするとき、
        // Σ_[d:1~9] s(d) を求めよ。
        // 
        // f(n,d),nのnについての単調増加性より、
        // 区間[a,b]での範囲[f(a,d),f(b,d)]と[a,b]が交わりを持たなければ、
        // [a,b]内にf(n,d)=nの解はない。
        // 
        // n=10^k-1のとき、f(n,d)=k*10^(k-1)となる。
        // k>=11のとき、つねにf(10^k-1,d)>10^(k-1)-1となるので、
        // f(n,d)=nの解は、n<10^11とわかる。
        // あとは上記の性質を利用して、解を2分探索して列挙すればよい。
        private function solve() : Number
        {
        		var s : Number = 1;
        		var g : Number = 1E11;
        		var ret : Number = 0;
        		for(var d : uint = 1;d <= 9;d++){
        			var ct : Number = rec(s, g, d, f(s, d), f(g, d));
        			tr(d, ct);
        			ret += ct;
        		}
        		return ret;
        }
        
        private function rec(s : Number, g : Number, d : uint, fs : Number, fg : Number) : Number
        {
        		if(g - s == 1){
//        			if(fs == s)tr(s);
        			return fs == s ? s : 0;
        		}
        		var m : Number = Math.floor((s + g) / 2);
        		var fm : Number = f(m, d);
        		// s < m < g
        		// fs < fm < fg
        		var ret : Number = 0;
        		if(!(fm < s || m < fs))ret += rec(s, m, d, fs, fm);
        		if(!(fg < m || g < fm))ret += rec(m, g, d, fm, fg);
        		return ret;
        }
        
        private function f(n : Number, d : uint) : Number
        {
        		var ret : Number = 0;
        		for(var k : Number = 1;k <= n;k *= 10){
        			ret += Math.floor(n/(k*10))*k;
        			var x : uint = (n / k) % 10;
        			if(d < x)ret += k;
//        			if(d == x)ret += (n-Math.floor(n/k)*k)+1;
        			if(d == x)ret += n%k+1;
        		}
        		return ret;
        }

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