最終更新: 2011-10-29T21:40+0900
何時間もかかるこれがどうやったら速くなるでしょうか？
いまは可能な組み合わせを全て試してみて、できあがった数字をカウントしてる。その後で素数を順番に辿って生成カウントが 1のものを足し合わせたものが答え。上限が 10倍になるごとにどえらく計算量が増える。かけ算ならまだしも足し算の組み合わせに有効な考え方を自分が全く持ち合わせていないことがこれまでの問題からも何となくわかってる。どうすんの？
# PE333
require 'mathn' # Primeが使いたいだけなのに。グローバルフラグは悪。
UPPERBOUND = 100_0000
EXP3_UPPERBOUND = (Math.log(UPPERBOUND)/Math.log(3)).floor+1
EXP2_UPPERBOUND = (Math.log(UPPERBOUND)/Math.log(2)).floor+1
# × 2^0 2^1 2^2 2^3 2^4 2^5 2^19
# 3^0 1 2 4 8 16 32 524288
# 3^1 3 6 12 24 48 96
# 3^2 9 18 36 72
# 3^3 27 54
# 3^4 81
# 3^5
# 3^12 531441
primes = Hash.new(0)
q = []
sum_of_q = lambda{
sum = 0
last_exp3 = EXP3_UPPERBOUND
q.each_with_index{|exp3,exp2|
next if exp3 == last_exp3
sum += (1<<exp2) * 3**exp3
last_exp3 = exp3
}
return sum
}
fill_q = lambda{
q.fill(q.last||EXP3_UPPERBOUND, q.length, EXP2_UPPERBOUND-q.length);
}
fill_q.call
until q.empty?
exp2, pow2 = q.length-1, 1<<(q.length-1)
next q.pop if q[exp2] == 0
q[exp2], pow3 = q[exp2]-1, 3**(q[exp2]-1)
sum = sum_of_q.call
q[exp2], pow3, sum = q[exp2]-1, pow3/3, sum-(2*pow2*pow3/3) while 0 <= q[exp2] and UPPERBOUND <= sum
next q.pop if q[exp2] < 0
primes[sum_of_q.call] += 1
fill_q.call
end
sum = 0
Prime.new.each{|pr|
break if UPPERBOUND <= pr
sum += pr if primes[pr] == 1
}
p sum
p Process.times #=> <struct Struct::Tms utime=25990.64, stime=150.806, cutime=0.0, cstime=0.0>