An Ordinary Sequence

問題

• https://yukicoder.me/problems/no/639
• 要約不要な程度には短いはず

解法

• 単純にメモ化再帰だけで良いです。これは、n/x/y == n/y/x (== n/(x*y)) がどのような自然数に対しても成立するため、当然 n/3/5 == n/5/3 となるからです。
• 証明は https://qiita.com/cielavenir/items/21a6711afd6be8c18c55 をご覧ください。

答案

• https://yukicoder.me/submissions/232565

$memo={0=>1}
def dfs(n)
	$memo[n]||=dfs(n/3)+dfs(n/5)
end
p dfs(gets.to_i)