Project Euler 274

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

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

        // n=10A+B(Bはnを10で割った余り)と表すと
        // f(n)=A+Bm. よって、任意の非負整数A,Bについて、
        // A+Bm=0(mod p) <=> 10A+B=0(mod p)が成り立つ。
        // B=-10Aを左の式に代入してA(1-10m)=0(mod p)
        // Aは任意なので、pと互いに素になるように選べて、<=> 1-10m=0(mod p)
        // 10m=1(mod p). よってmはpを法として10の逆元。
        // あとは各pについて拡張ユークリッド互除法を使って逆元を求めていって足せばよい。
        // もうちょい証明が必要な気もするけどたぶん自明・・
        private function solve(N : uint) : Number
        {
            var primes : Array = doEratosthenes(N);
            
            var sum : Number = 0;
            for each(var p : uint in primes){
                var e : Array = exGCD(10, p);
                if(e[0] != 1)continue;
                var m : uint = (e[1] + p) % p;
                sum += m;
            }
            return sum;
        }

        private function doEratosthenes(n : int) : Array
        {
            var nn : uint = ((n / 2 - 1) >>> 5) + 1;
            var ar : Vector.<uint> = new Vector.<uint>(nn);
            var i : uint, j : uint;
            for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
            ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
            
            var sq : uint = (Math.sqrt(n) - 3) >>> 1;
            for(var p : uint = 0;p <= sq;p++){
                if(ar[p >>> 5] & (1 << (p & 31))){
                    var m : uint = (p << 1) + 3;
                    var m2 : uint = m << 1;
                    for(var mm : uint = m * m;mm <= n;mm += m2){
                        var ind : uint = (mm - 3) >>> 1;
                        ar[ind >>> 5] &= ~(1 << (ind & 31));
                    }
                }
            }
            
            var ret : Array = [2];
            for(i = 0;i < nn;i++){
                for(j = 0;j <= 31;j++){
                    if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
                }
            }
            return ret;
        }
        
        private function exGCD(a : int, b : int) : Array
        {
            var p : int = 1, q : int = 0;
            var r : int = 0, s : int = 1;
            while(b > 0){
                var c : int = a / b;
                var d : int = a;
                a = b;
                b = d % b;
                
                d = p;
                p = q;
                q = d - c * q;
                
                /*
                d = r;
                r = s;
                s = d - c * s;
                */
            }
//            return [a, p, r];
            return [a, p];
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}