素数で作る天秤ばかり

素数で作る天秤ばかり

2016/09/20 10:00 AM なので，その 1 分後に投稿されるように予約

【問題】
天秤ばかりを使って重さを量りたいと考えています。
ただし、使えるおもりは重さが素数のものしかありませんでした。

m, n をともに正の整数とし、m 以下の素数すべてがおもりの重さとして1つずつ用意されているとき、n グラムの計り方が何通りあるかを求めてください。

例えば、m = 10, n = 2のとき、2, 3, 5, 7 のおもりが一つずつありますので、左右に以下のおもりを使った4通りがあります。
（量るものを左側に置いたとします。）

左側     　　　　右側
なし     　　　　「2」
「3」     　　　　「5」
「5」     　　　　「7」
「2」、「3」     「7」

標準入力から m と n がスペースで区切って与えられるとき、n グラムの計り方が何通りあるかを標準出力に出力してください。
（ただし、 m < 50 とします。）

【入出力サンプル】
標準入力
10 2

標準出力
4


==========

bin を毎回呼び出すとそのオーバーヘッドがあるので，結果をリスト bin.list に保存しておき，関数呼び出しをリストの参照に換えることで，実行時間は速くなる

bin = function(p) {
    retval = matrix(0L, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0L, (2^p/2^n)), rep(1L, (2^p/2^n))), length = 2^p)
    }
    retval
}

f = function(m, n) {
    bin.list = sapply(1:14, bin)
    count = 0
    prime = c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
    prime = prime[m >= prime]
    left.use = bin.list[[length(prime)]] # bin(length(prime))
    left = left.use %*% prime + n
    for (i in 1:(nrow(left.use) - 1)) {
        rest = prime[!left.use[i, ]]
        if (sum(rest) >= left[i]) {
            right.use = bin.list[[length(rest)]] # bin(length(rest))
            right = right.use %*% rest
            count = count + sum((left[i] == right))
        }
    }
    cat(count)
}


f(10, 2)  # 4
f(20, 10) # 90
f(30, 50) # 286
f(40, 30) # 3217
f(46, 3)  # 24946