Counting Factor Trees (ZOJ Problem Set - 3405)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3405

問題

整数Nを素因数分解したい。図のようにNを素因数分解する時に2つの数値ずつに分けることを繰り返して計算を行う。分解の仕方は何通りか？
2<=N<=1000000000
答えは64bit signed integerに収まる。

解法

葉の並べ方と木の構築の仕方を考えれば良い。木の構築の仕方はカタラン数になる。