Project Euler 281

@see http://projecteuler.net/index.php?section=problems&id=281

by uwi 05 Mar 2010

Embed

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

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

        // 円形のピザをmn個に分ける。
        // f(m,n)を、mn個のピザ片をn個ずつの異なるm色で色分けする組み合わせとする。
        // ただし、回転して一致するものは同一とみなし、鏡で反転？して一致するものは違うものとする。
        // (m>=2, n>=1)
        // f(m,n)<=10^15となるf(m,n)の合計を求めよ。
        // 
        // 基本的には(mn)!/(n!)^mを回転分のmnで割った数。
        // だが、同じパターンが何連続かしている場合は、
        //　mn/周期で割ってやらないといけない。
        private function solve(LIM : Number) : Array
        {
        		var sum : Array = [0, 0];
        		var fact : Number = 2;
        		for(var m : uint = 2; fact < LIM;m++){
        			for(var n : uint = 1;;n++){
        				var val : Number = f(m, n);
        				if(val >= LIM)break;
        				tr(m,n,val);
        				N2.inc(sum, val);
        			}
        			fact *= m;
        		}
        		return sum;
        }
        
		// f(m,n)=Σ_[d|n] h(m,d)/md
		// h(m,d)=g(m,d)-Σ_[u|d, u≠d] h(m,u)
        private function f(m : uint, n : uint) : Number
        {
        		var divides : Array = [];
        		var d : uint, u : uint;
        		// nの約数を列挙
        		for(d = 1;d * d <= n;d++){
        			if(n % d == 0){
        				divides.push(d);
        				if(d * d != n)divides.push(n / d);
        			}
        		}
        		divides.sort(Array.NUMERIC);
        		
        		var sum : Number = 0;
        		var hs : Object = {};
        		// nの約数dについて帰納的にh(m,d)を求めていく。
        		for each(d in divides){
        			var val : Number = g(m, d);
        			for each(u in divides){
        				if(u == d)break;
        				if(d % u == 0)val -= hs[u];
        			}
//        			tr(d, val, val / m / d, g(m, d));
        			sum += val / m / d;
        			hs[d] = val;
        		}
        		
        		return sum;
        }
        
        // g(m,n)=(mn)!/(n!)^m
        private function g(m : uint, d : uint) : Number
        {
        		var i : uint, j : uint;
        		var factMD : Number = 1;
        		for(i = 1;i <= d;i++){
        			for(j = 0;j < m;j++){
        				factMD *= (m*i-j);
        			}
        			for(j = 0;j < m;j++){
        				factMD /= i;
        			}
        		}
        		return factMD;
        }

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

class N2{
	public static const N : Number = 1E15;	
	public static function add(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] + b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + b[1] + rp;
		return [r0, r1];
	}
	
	public static function sub(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] - b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] - b[1] + rp;
		return [r0, r1];
	}
	
	public static function inc(a : Array, b : Number) : Array
	{
		var r0 : Number = a[0] + b;
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + rp;
		
		a[0] = r0;
		a[1] = r1;
		return a;
	}
}