Project Euler 266

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=266
    
    // 190以下の素数の積をPとして、
    // √Pより小さいPの約数のうち、最大のものの下16桁を求める。
    //
    // log化すると、190以下の素数のlog値 42個をつかって、
    // 0.5logPより小さい最大の和を作る問題になるが、探索空間が2^42なので一筋縄ではいかない。
    // 21個ずつに分け、それぞれの作りうる和2^21個ずつを生成してから一方をソートし、
    // ソートしていない方の値それぞれについて、ソートしている方から条件を満たす最大の数を二分探索する。
    public class Euler266 extends Sprite {
        private var _tf : TextField;
  
        public function Euler266() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(190));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private function solve(N : int) : MPI
        {
            // 素数列挙
            var primes : Array = doEratosthenes(N);
            var n : int = primes.length;
            tr(n); 
            var i : int, j : int;
            
            // logに変換
            var targ : Number = 0;
            var lp : Array = new Array(n);
            for(i = 0;i < n;i++){
                lp[i] = Math.log(primes[i]);
                targ += lp[i];
            }
            targ *= 0.5;
            
            var offset : int = n / 2;
            
            // 和生成・ソート
            var ef : Vector.<Number> = expandNumber(lp.slice(0, offset));
            var eb : Vector.<Number> = expandNumber(lp.slice(offset, n));
            var oeb : Vector.<Number> = eb.concat();
            eb.sort(Array.NUMERIC);
            
            // 最大和の探索
            var min : Number = Number.MAX_VALUE;
            var minf : uint;
            var minb : uint;
            for(i = 0;i < ef.length;i++){
                var v : Number = targ - ef[i];
                var s : uint = 0;
                var g : uint = eb.length;
                do{
                    var m : uint = (s + g) >> 1;
                    if(eb[m] < v){
                        s = m;
                    }else{
                        g = m;
                    }
                }while(g - s > 1);
                
                var sub : Number = v - eb[s];
                if(sub > 0 && sub < min){
                    min = sub;
                    minf = i;
                    minb = s;
                }
            }
            
            // 素因数に戻す・積を求める
            var a : Array = [];
            var lpp : Number = 0; // 検算用
            var mul : MPI = new MPI(1);
            
            var indf : int = minf;
            var indb : int = oeb.indexOf(eb[minb]); // expandNumberで生成直後のインデックスを求める
            for(i = indf, j = 0;i > 0;i >>>= 1, j++){
                if(i & 1){
                    lpp += Math.log(primes[j]);
                    mul = MPI.mulint(mul, primes[j]);
                    a.push(primes[j]);
                }
            }
            for(i = indb, j = offset;i > 0;i >>>= 1, j++){
                if(i & 1){
                    lpp += Math.log(primes[j]);
                    mul = MPI.mulint(mul, primes[j]);
                    a.push(primes[j]);
                }
            }
            tr(a);
            tr(min);
            tr(lpp);
            tr(targ);
            return mul;
        }
        
        private function expandNumber(a : Array) : Vector.<Number>
        {
            var ret : Vector.<Number> = new Vector.<Number>(1 << a.length);
            ret[0] = 0;
            for(var i : int = 0;i < a.length;i++){
                var lim : int = 1 << i;
                for(var j : int = lim - 1;j >= 0;j--){
                    ret[j + lim] = ret[j] + a[i];
                }
            }
            return ret;
        }
        
        /*
        private function solve() : Number
        {
            var primes : Array = doEratosthenes(190);
            var n : int = primes.length;
            tr(n);
            var lp : Array = new Array(n);
            var i : int;
            
            var targ : Number = 0;
            for(i = 0;i < n;i++){
                lp[i] = Math.log(primes[i]);
                targ += lp[i];
            }
            targ *= 0.5;
            
            var offset : int = n / 2;
            
            var ef : Array = expand(lp.slice(0, offset));
            var eb : Array = expand(lp.slice(offset, n));
            ef.sortOn("0", Array.NUMERIC);
            eb.sortOn("0", Array.NUMERIC);
            
            var min : Number = Number.MAX_VALUE;
            var mini : uint;
            var mins : uint;
            for(i = 0;i < ef.length;i++){
                var v : Number = targ - ef[i][0];
                if(v < 0)break;
                var s : uint = 0;
                var g : uint = eb.length;
                do{
                    var m : uint = (s + g) >> 1;
                    if(eb[m][0] < v){
                        s = m;
                    }else{
                        g = m;
                    }
                }while(g - s > 1);
                
                var sub : Number = v - eb[s][0];
                if(sub > 0 && sub < min){
                    min = sub;
                    mini = i;
                    mins = s;
                }
//                tr(v, s, eb[s]);
            } 
            
            var mul : Number = 1;
            var a : Array = [];
            for each(i in ef[mini][1]){
                mul *= primes[i];
                mul %= 10000000000000000;
                a.push(primes[i]);
            }
            for each(i in eb[mins][1]){
                mul *= primes[i + offset];
                mul %= 10000000000000000;
                a.push(primes[i + offset]);
            }
            tr(a);
            tr(min);
            return mul;
        }
        */
        
        private function expand(a : Array) : Array
        {
            var ret : Array = new Array(1 << a.length);
            ret[0] = [0, []];
            for(var i : int = 0;i < a.length;i++){
                var lim : int = 1 << i;
                for(var j : int = lim - 1;j >= 0;j--){
                    ret[j + lim] = [ret[j][0] + a[i], ret[j][1].concat(i)];
                }
            }
            return ret;
        }
        
        private static function doEratosthenes(n : int) : Array
        {
            var ar : Vector.<uint> = new Vector.<uint>(n / 2 - 1);
            var i : int;
            for(i = 0;i < ar.length;i++)ar[i] = 1;
            
            var sq : int = (Math.sqrt(n) - 3) >> 1;
            for(var p : int = 0;p <= sq;p++){
                if(ar[p] == 1){
                    var m : int = (p << 1) + 3;
                    var m2 : int = m << 1;
                    for(var mm : int = m * m;mm <= n;mm += m2){
                        ar[(mm - 3) >> 1] = 0;
                    }
                }
            }
            var ret : Array = [2];
            for(i = 0;i < ar.length;i++){
                if(ar[i] == 1)ret.push((i << 1) + 3);
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}

class MPI
{
    public var d : Vector.<uint>;
    
    public function MPI(v : * = 0)
    {
        if(v is Number){
            d = Vector.<uint>([]);
            for(var n : Number = v;n != 0;n = Math.floor(n / 10))d.push(n % 10);
            if(v == 0)d.push(0);
        }else if(v is String){
            d = Vector.<uint>([]);
            for(var i : int = v.length - 1;i >= 0;i--){
                d.push(uint(v.charAt(i)));
            }
        }else if(v is Array){
            d = Vector.<uint>(v);
        }else if(v is Vector.<uint>){
            d = v.concat();
        }else if(v is MPI){
            d = v.d.concat();
        }
        if(d)shave();
    }
    
    public static function add(a : MPI, b : MPI) : MPI
    {
        var ret : MPI = new MPI(a);
        var i : int;
        var minl : int = Math.min(ret.d.length, b.d.length);
        for(i = 0;i < minl;i++){
            ret.d[i] += b.d[i];
        }
        for(i = ret.d.length;i < b.d.length;i++){
            ret.d.push(b.d[i]);
        }
        ret.carry();
        return ret;
    }
    
    public static function addint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        ret.d[0] += b;
        ret.carry();
        return ret;
    }
    
    public function addint_(b : int) : MPI
    {
        this.d[0] += b;
        this.carry();
        return this;
    }
    
    public function inc() : void
    {
        d[0]++;
        for(var i : int = 0;i < d.length;i++){
            if(d[i] >= 10){
                var c : uint = d[i] / 10;
                if(i == d.length - 1){
                    d.push(0);
                }
                d[i + 1] += c;
                d[i] %= 10;
            }else{
                break;
            }
        }
    }
    
    public static function sub(a: MPI, b : MPI) : MPI
    {
        if(comp(a, b) < 0){
            var m : MPI = a; a = b; b = m;
        }
        // a - b
        var ret : MPI = new MPI(a);
        var i : int;
        for(i = 0;i < b.d.length;i++){
            ret.d[i] -= b.d[i];
        }
        
        ret.minuscarry();
        return ret;
    }
    
    public static function subint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        ret.d[0] -= b;
        ret.minuscarry();
        return ret;
    }
    
    public function subint_(b : int) : MPI
    {
        this.d[0] -= b;
        this.minuscarry();
        return this;
    }
    
    public static function comp(a : MPI, b : MPI) : int
    {
        if(a.d.length != b.d.length)return a.d.length - b.d.length;
        for(var i : int = a.d.length - 1;i >= 0;i--){
            if(a.d[i] != b.d[i]){
                return a.d[i] - b.d[i];
            }
        }
        return 0;
    }
    
    public static function mul(a : MPI, b : MPI) : MPI
    {
        var retv : Vector.<uint> = new Vector.<uint>(a.d.length + b.d.length);
        var i : int, j : int;
        for(i = 0;i < retv.length;i++)retv[i] = 0;
        for(i = 0;i < a.d.length;i++){
            for(j = 0;j < b.d.length;j++){
                retv[i + j] += a.d[i] * b.d[j];
            }
        }
        var ret : MPI = new MPI(retv);
        ret.carry();
        ret.shave();
        return ret;
    }
    
    public static function mulint(a : MPI, b : int) : MPI
    {
        var ret : MPI = new MPI(a);
        for(var i : int = 0;i < ret.d.length;i++){
            ret.d[i] *= b;
        }
        ret.carry();
        return ret;
    }
    
    public function mulint_(b : int) : MPI
    {
        for(var i : int = 0;i < d.length;i++){
            this.d[i] *= b;
        }
        this.carry();
        return this;
    }
    
    public static function div(a : MPI, b : MPI) : Array
    {
        var bm : Array = new Array(10);
        var i : int, j : int;
        for(i = 1;i <= 9;i++)bm[i] = mulint(b, i);
        
        var retr : Vector.<uint> = Vector.<uint>([]);
        var m : MPI = new MPI(0);
        for(i = a.d.length - 1;i >= 0;i--){
            m = addint(mulint(m, 10), a.d[i]);
            for(j = 1;j <= 9;j++){
                if(comp(m, bm[j]) < 0)break;
            }
            retr.push(j - 1);
            if(j >= 2)m = sub(m, bm[j - 1]);
        }
        
        var ret : MPI = new MPI(retr.reverse());
        ret.shave();
        m.shave();
        return [ret, m];
    }
    
    public static function divint(a : MPI, b : int) : Array
    {
        var i : int;
        
        var retr : Vector.<uint> = Vector.<uint>([]);
        var m : int = 0;
        for(i = a.d.length - 1;i >= 0;i--){
            m = m * 10 + a.d[i];
            var dv : int = m / b;
            retr.push(dv);
            m %= b;
        }
        
        var ret : MPI = new MPI(retr.reverse());
        ret.shave();
        return [ret, m];
    }
    
    // 末尾の0の個数
    public function nLast0() : int
    {
        for(var i : int = 0;i < d.length && d[i] == 0;i++);
        return i;
    }
    
    // 位上げ
    public function carry() : void
    {
        for(var i : int = 0;i < d.length;i++){
            if(d[i] >= 10){
                var c : uint = d[i] / 10;
                if(i == d.length - 1){
                    d.push(0);
                }
                d[i + 1] += c;
                d[i] %= 10;
            }
        }
    }
    
    // 位下げ
    public function minuscarry() : void
    {
        for(var i : int = 0;i < d.length;i++){
            if(d[i] <= 2147483648)continue; // やっつけ
            var v : int = d[i] - 4294967296;
            var c : int = (-v + 9) / 10;
            d[i + 1] -= c;
            d[i] += 10 * c;
        }
        shave();
    }
    
    // 上位の桁から0を削る
    public function shave() : void
    {
        for(var i : int = d.length - 1;i >= 1;i--){
            if(d[i] > 0)break;
            d.pop();
        }
    }
    
    public function toString() : String
    {
        return d.concat().reverse().join('');
    } 
}