Project Euler 186

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

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

        // O(N)にしてみた。
        private function solve() : int
        {
            var ngroup : Array = new Array(1000000); // グループの要素数
            var refs : Array = new Array(1000000); // こいつと同じグループ
            var i : int;
            for(i = 0;i < 1000000;i++){
                ngroup[i] = 1;
                refs[i] = i;
            }
            var rpm : int = 524287; // Prime Ministerのグループの主
            for(var r : int = 1;r <= 3000000;r++){
                var caller : int = S();
                var called : int = S();
//                tr(caller, called);

                // かけ間違いはノーカウント
                if(called == caller){
                    r--;
                    continue;
                }
                // グループの主をさがす。グループ番号と要素番号が同じのが主
                for(var rd : int = called;refs[rd] != rd;rd = refs[rd]);
                for(var rr : int = caller;refs[rr] != rr;rr = refs[rr]);
                refs[called] = rd;
                refs[caller] = rr;
                
                // より低い方にグループを集める
                if(rr == rd){
                    continue;
                }
                if(rr > rd){
                    var d : int = rr;
                    rr = rd;
                    rd = d;
                }
                
                // root_called -> root_caller
                refs[rd] = rr;
                ngroup[rr] += ngroup[rd];
                
                // Prime Ministerを含むグループならカウントしなおす
                if(rpm == rr || rpm == rd){
                    rpm = rr;
                    if(ngroup[rpm] >= 990000)break;
                }
            }
            tr(r, ngroup[rpm]);
            return r;
        }
        
        private var _k : int = 1;
        private var _shis : Array = new Array(64);
        
        private function S() : int
        {
            var ret : int = _k <= 55 ?
                (mod1M(mod1M(300007, _k * _k) - 200003, _k) + 100003) % 1000000 :
                (_shis[(_k + 40) & 63] + _shis[(_k + 9) & 63]) % 1000000;
            _shis[_k & 63] = ret;
            _k++;
            return ret;
        }
        
        private function mod1M(a : int, b : int) : int
        {
            if(a < 0)a += 1000000; // やっつけ
            if(b < 0)b += 1000000;
            var aa : int = a / 1000;
            var ab : int = a % 1000;
            var ba : int = b / 1000;
            var bb : int = b % 1000;
            return (((ab * bb) % 1000000) + ((ab * ba + aa * bb) % 1000) * 1000) % 1000000;
        }

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