/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/zBKVq
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=269
public class Euler269 extends Sprite {
private var _tf : TextField;
public function Euler269() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
// tr(test());
tr(solve());
var g : int = getTimer();
tr((g - s) + " ms");
}
private const N : int = 16;
// まずP(x)=0の解はx<=0に限られ、さらに
// 最上位の項はx<=-10で他の項で抑えきれなくなるから、
// 整数解は-9,..,0に限られる。
//
// Z(10^N)を求める。
// まず解0の場合、定数項が0なので10^(N-1)通り。
// それ以外の解xの場合、下位の項から、幅優先で数えていく。
// 次の位に行くときに-xの倍数になっていないといけない。
//
// そして、解を2つ以上含むP(x)の個数を数える。
// 各係数の範囲は0-9なので、最大3つまで考えればよい。(1*2*3<=9<1*2*3*4)
// 解を2つ含む場合の個数を引き、
// 解を3つ含む場合の個数を足せばOK
private function solve() : Number
{
var i : uint, j : uint, k : uint, l : uint;
var val : Number;
// x = 0
var ret : Number = Math.pow(10, N - 1);
// x = -9,...,-1
for(j = 1;j <= 9;j++){
val = rec(j);
tr(j, val);
ret += val;
}
// 解が2個
for(j = 1;j <= 9;j++){
for(k = j + 1;k <= 9;k++){
if(j * k <= 9){
_cache2 = new Array(N);
for(i = 0;i < N;i++)_cache2[i] = [];
val = rec2([0, 0], 0, [1, j + k, j * k]);
tr(j, k, val);
ret -= val;
}
}
}
// 解が3個
for(j = 1;j <= 9;j++){
for(k = j + 1;k <= 9;k++){
for(l = k + 1;l <= 9;l++){
if(j * k * l <= 9){
_cache3 = new Array(N);
for(i = 0;i < N;i++)_cache3[i] = [];
val = rec3([0, 0, 0], 0, [1, j + k + l, j * k + k * l + l * j, j * k * l]);
tr(j, k, l, val);
ret += val;
}
}
}
}
return ret;
}
private function rec(d : int) : Number
{
// wfs
var first : Boolean = true;
var seed : Object = {0 : 1};
var next : Object = {};
for(var i : uint = 0;i < N;i++){
for(var key : String in seed){
var k : int = int(key);
var v : Number = seed[key];
for(var j : int = first ? 1 : 0;j <= 9;j++){
if((k + j) % d == 0){
var nk : int = -(k + j) / d;
if(!next[nk])next[nk] = 0;
next[nk] += v;
}
}
}
seed = next;
next = {};
first = false;
}
return seed[0];
}
private var _cache2 : Array;
private function rec2(prev : Array, depth : uint, cors : Array) : Number
{
// dfs
if(depth == N){
return (prev[0] == 0 && prev[1] == 0) ? 1 : 0;
}
if(_cache2[depth][prev[0]] && _cache2[depth][prev[0]][prev[1]] != null){
return _cache2[depth][prev[0]][prev[1]];
}
var ret : Number = 0;
var i : int;
var max : int = Math.floor((9 - prev[1]) / cors[2]);
var min : int = Math.ceil((0 - prev[1]) / cors[2]);
for(i = min;i <= max;i++){
if(depth == 0 && i == 0)continue; // 最下位0は無視
var a : int = cors[0] * i;
var b : int = cors[1] * i + prev[0];
var c : int = cors[2] * i + prev[1];
ret += rec2([a, b], depth + 1, cors);
}
if(!_cache2[depth][prev[0]])_cache2[depth][prev[0]] = [];
_cache2[depth][prev[0]][prev[1]] = ret;
return ret;
}
private var _cache3 : Array;
private function rec3(prev : Array, depth : uint, cors : Array) : Number
{
if(depth == N){
return (prev[0] == 0 && prev[1] == 0 && prev[2] == 0) ? 1 : 0;
}
if(_cache3[depth][prev[0]] && _cache3[depth][prev[0]][prev[1]] && _cache3[depth][prev[0]][prev[1]][prev[2]] != null){
return _cache3[depth][prev[0]][prev[1]][prev[2]];
}
var ret : Number = 0;
var i : int;
var max : int = Math.floor((9 - prev[2]) / cors[3]);
var min : int = Math.ceil((0 - prev[2]) / cors[3]);
for(i = min;i <= max;i++){
if(depth == 0 && i == 0)continue; // 最下位0は無視
var a : int = cors[0] * i;
var b : int = cors[1] * i + prev[0];
var c : int = cors[2] * i + prev[1];
// var d : int = cors[3] * i + prev[2];
ret += rec3([a, b, c], depth + 1, cors);
}
if(!_cache3[depth][prev[0]])_cache3[depth][prev[0]] = [];
if(!_cache3[depth][prev[0]][prev[1]])_cache3[depth][prev[0]][prev[1]] = [];
_cache3[depth][prev[0]][prev[1]][prev[2]] = ret;
return ret;
}
private function test() : Number
{
var ret : uint = 0;
for(var a : uint = 1;a <= 9;a++){
for(var b : uint = 0;b <= 9;b++){
for(var c : uint = 0;c <= 9;c++){
for(var d : uint = 0;d <= 9;d++){
for(var e : uint = 0;e <= 9;e++){
if(ok(e,d,c,b,a,-1) && ok(e,d,c,b,a,-2)){
ret++;
}
/*
for(var x : int = -9;x <= 0;x++){
if(ok(e,d,c,b,a,x)){
ret++;
break;
}
}
*/
}}}}}
return ret;
}
private function ok(e : int, d : int, c : int, b : int, a : int, x : int) : Boolean
{
return ((((e * x + d) * x + c) * x + b) * x + a) == 0;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
