平方数の和で表す平方数
締め切りが 12月08日(火)AM10:00 なので,解答例をその 1 分後に公開。
【問題】
全ての自然数は高々四個の平方数の和で表される、という「四平方定理」が知られています。
例えば、15という数は9+4+1+1、つまり3^2+2^2+1^2+1^2と表されます。
今回は「平方数」を「ちょうど四個の平方数」で表す、ということを考えてみます。
例えば、36という平方数は、以下のように二通りの足し算で表すことができます。
※ここでは足し算の順序は考えないものとします。
25+9+1+1、つまり5^2+3^2+1^2+1^2
9+9+9+9、つまり3^2+3^2+3^2+3^2
しかし、16という平方数は、以下の一通りしか表現できません。
4+4+4+4、つまり2^2+2^2+2^2+2^2
標準入力から整数nが与えられた時、n以下の平方数のうち、
上記のように一通りでしか表現できないものがいくつあるかを標準出力に出力してください。
【入出力サンプル】
標準入力
25
標準出力
3
※4, 16, 25の3通り
最後は,expand.grid(a^2, a^2, a^2, a^2) を expand.grid(a*a, a*a, a*a, a*a) にして,実行時間を縮めた。
前者は numeric 後者は integer。ギリギリのところで計算時間が短縮された。
con = file("stdin", "r"); n = as.integer(readLines(con, 1))
a = seq_len(floor(sqrt(n)+.Machine$double.eps))
p = expand.grid(a*a, a*a, a*a, a*a) ###
s = rowSums(p) ###
o = s %in% a^2
p = p[o,]
s = s[o]
m = sapply(split(p, s), function(x) {
nr = nrow(x)
if (nr > 24) {
FALSE
} else if (nr == 1) {
TRUE
} else {
nrow(unique(t(apply(x, 1, sort)))) == 1
}
})
cat(sum(m))