Project Euler 182

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.*;
    import com.bit101.components.*;
    
    // @see http://projecteuler.net/index.php?section=problems&id=182
    public class Euler182 extends Sprite {
        private var _tf : TextField;
  
        public function Euler182() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var pb : PushButton = new PushButton(this, 350, 10);
            pb.label = "stop";
            pb.width = 100;
            pb.addEventListener(MouseEvent.CLICK, function(e : MouseEvent) : void
            {
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
            });
            
            _s = getTimer();
            solve(1009, 3643);
//            check(7, 11);
            var g : int = getTimer();
            tr((g - _s) + " ms");
        }
        
        private var _s : int;
        private var ra : Array;
        private var rb : Array;

        private var ct : Array;
        private var N : int;
        private var A : int;
        private var B : int;
        private var PHI : int;
        
        private function check(A : int, B : int) : void
        {
            var N : int = A * B;
            var ddd : Array = enumDs((A - 1) * (B - 1));
            for(var i : int = 1;i < N;i++){
                var f : Boolean = false;
                for each(var d : int in ddd){
                    if(i % d == 0){
                        f = true;
                        break;
                    }
                } 
                if(f)continue;
                
                var c : int = 0;
                for(var j : int = 1;j < N;j++){
                    if(exmod(j, i, N) == j){
                        c++;
                    }
                }
                tr(i, c);
            }
        }
        
        // n = pq.
        // GCD(m, n)=1であるmについて、mの逆元はただ1つしか存在しないので
        // m^e=m(mod n)⇔m^(e-1)=1(mod n)
        // ⇔m^(e-1)=1(mod p)かつm^(e-1)=1(mod q)
        // pを法としてm^(e-1)=1をみたすm,eをm_p,e_p,
        // qについてのそれをm_q,e_qとおくと、
        // もとのmはm=m_q^-1 m_p + m_p^-1 m_q,
        // またeは、e-1=LCM(e_p - 1, e_q - 1)で表される。
        // ここではmはどうでもよい(m_p,m_qを網羅すればmを網羅したことになる)ので、
        // eだけ求めればよい。
        // フェルマーの小定理より、e_p-1はp-1のある約数の定数倍で表されるので、
        // これを利用して高速に求める。
        //
        // 次に、GCD(m, n)≠1であるmについて、m=kpとすると、
        // (kp)^e=kp(mod n)⇔(kp)^(e-1)=1(mod q)なので、
        // 上と同じくe_qたちを求めればよい。mがqの倍数の場合も同様。
        private function solve(A : int, B : int) : void
        {
            this.A = A;
            this.B = B;
            N = A * B;
            PHI = (A - 1) * (B - 1);
            
            var da : Array = enumDivider(A - 1);
            var db : Array = enumDivider(B - 1);
            
            var m : int, e : int;
            ra = new Array(A);
            for(m = 1;m < A;m++){
                for each(e in da){
                    if(exmod(m, e, A) == 1){
                        ra[m] = e;
                        break;
                    }
                }
            }
            rb = new Array(B);
            for(m = 1;m < B;m++){
                for each(e in db){
                    if(exmod(m, e, B) == 1){
                        rb[m] = e;
                        break;
                    }
                }
            }

            ct = new Array(PHI);
            var i : int;
            for(i = 0;i < PHI;i++)ct[i] = 0;
            
            var a : int, b : int;
            for(b = 1;b < B;b++){
                for each(e in db){
                    if(exmod(b, e, B) == 1){
                        for(i = 1 + e;i < PHI;i += e){
                            ct[i]++;
                        }
                        break;
                    }
                }
            }
            
            for(a = 1;a < A;a++){
                for each(e in da){
                    if(exmod(a, e, A) == 1){
                        for(i = 1 + e;i < PHI;i += e){
                            ct[i]++;
                        }
                        break;
                    }
                }
            }
            
            _a = 1;
            
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private var _a : int;
        
        private function onEnterFrame(_e : Event) : void
        {
            var b : int, e : int;
            for(b = 1;b < B;b++){
//                    m = (invb * a + inva * b) % N;
                var step : int = ra[_a] * rb[b] / GCD(ra[_a], rb[b]);
                for(e = 1 + step;e < PHI;e += step){
                    ct[e]++;
                }
            }
            if(_a % 40 == 0)tr(_a, (getTimer() - _s) + "ms");
            _a++;
            if(_a == A){
                removeEventListener(Event.ENTER_FRAME, onEnterFrame);
                postprocess();
            }
        }
            
	private static function GCD(a : int, b : int) : int
	{
	    while(b > 0){
	        var d : int = a;
	        a = b;
	        b = d % b;
	    }
	    return a;
	}
	            
         private function postprocess() : void
         {
            var min : int = N;
            var ret : Number = 0;
            var ddd : Array = enumDs(PHI);
            var i : int;
                        
            for(i = 2;i < PHI;i++){
                var f : Boolean = false;
                for each(var d : int in ddd){
                    if(i % d == 0){
                        f = true;
                        break;
                    }
                } 
                if(f)continue;
                
                if(ct[i] < min){
                    min = ct[i];
                    ret = 0;
                }
                if(ct[i] == min){
                    ret += i;
                }
            }
            
            tr("min", min);
            tr("ret", ret);
            tr((getTimer() - _s) + "ms");
        }
        
        private function enumDivider(n : int) : Array
        {
            var ret : Array = [];
            var sq : int = Math.sqrt(n);
            for(var i : int = sq;i >= 1;i--){
                if(n % i == 0){
                    ret.push(i);
                    if(i != sq)ret.push(n / i);
                }
            }
            ret.sort(Array.NUMERIC);
            return ret;
        }
        
        private function enumDs(n : int) : Array
        {
            var sq : int = Math.sqrt(n);
            var ret : Array = [];
            for(var i : int = 2;i <= sq;i++){
                if(n % i == 0){
                    while(n % i == 0)n /= i;
                    ret.push(i);
                    sq = Math.sqrt(n);
                }
            }
            ret.push(n);
            return ret;
        }
        
        private function exmod(a : int, n : int, p : int) : int
        { 
            var mul : Number = a;
            var ret : Number = 1;
            for(var i : int = 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;
        }
    }
}