Project Euler 168

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=168
    public class Euler168 extends Sprite {
        private var _tf : TextField;
  
        public function Euler168() {
            _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");
        }

        // 1つの整数Nのうち、最下位の桁の値をB(1~9), それ以外の桁の値をAとする。
        // Nがn桁とすると、
        // 題意より 10A+B | 10^(n-1)*B+A (P)となるNを見つければよい。
        // ここで、10(10^(n-1)*B+A)-(10A+B)=(10^n-1)Bより、
        // Pが成立するならば、 10A+B | (10^n-1)B (Q)が成立する。
        //
        // Qが成立するようなNをさがす。
        // (10^n-1)Bは最大でn+1桁、10A+Bはn桁なので、両者の商は2桁以内となる。
        // これをCとおくと、0.1<B/C<=1.0
        // また、Pが成立するとき、Qでの商は10M-1(M=1,~,9)と表されるので
        // C=10M-1
        // (C=10M-1とQからPが成り立つと思うけど証明してない)
        // 
        // 以上の条件でさがして足す。
        private function solve() : int
        {
            var cycles : Array = new Array(100); // 10^n-1がindexで割り切れる桁数の周期
            var lasts : Array = new Array(100); // 10^n-1がindexで割り切れるときの商の下5桁
            for(var i : int = 1;i <= 99;i++){
                var v : int = 0;
                var c : int;
                var his : Array = new Array(100);
                for(c = 0;!his[v];c++, his[v] = true, v = (10 * v + 9) % i);
                cycles[i] = v == 0 ? c : 0;
                if(v == 0){
                    for(var j : int = 1;j <= 99999 && (i * j) % 100000 < 99999;j++);
                    lasts[i] = j;
                }
            }
            
            var sum : int = 0;
            // 5~100桁
            for(var B : int = 1;B <= 9;B++){
                for(var C : int = 9;C <= 89;C+=10){
                    if(0.1 < B/C && B/C <= 1.0){
                        // r=BとCの公約数
                        for(var r : int = B;r >= 2;r--){
                            if(B / r == 1 && int(C / r) == C / r){
                                break;
                            }
                        }
                        if(cycles[C/r] > 0){
                            var d : int = (int(100 / cycles[C/r]) - int((5 - 1) / cycles[C/r])) * lasts[C/r] * B/r;
                            tr(B, C, C/r, cycles[C/r], lasts[C/r] * B/r, d);
                            sum = (sum + d) % 100000;
                        }
                    }
                }
            }
            
            // 2~4桁
            var dg : int = 2;
            var dgb : int = 100;
            for(i = 11;i <= 9999;i++){
                if(i == dgb){
                    dg++;
                    dgb *= 10;
                }
                var P : int = (dgb / 10) * (i % 10) + int(i / 10);
                if(P / i == int(P / i)){
//                    tr(i);
                    sum = (sum + i) % 100000;
                }
            }
            return sum;
        }

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