U135020 数字分解2

这道题很简单，因此放在第一题作为水题并强制 O2。

哥德巴赫 1742 年给欧拉的信中哥德巴赫提出了以下猜想：任一大于 2 的整数都可写成三个质数之和。但是哥德巴赫自己无法证明它，于是就写信请教赫赫有名的大数学家欧拉帮忙证明，但是一直到死，欧拉也无法证明。因现今数学界已经不使用“ 1 也是素数”这个约定，原初猜想的现代陈述为：任一大于 5 的整数都可写成三个质数之和。( $n>5$：当 $n$ 为偶数，$n=2+(n-2)$，$n-2$ 也是偶数，可以分解为两个质数的和；当 $n$ 为奇数，$n=3+(n-3)$，$n-3$ 也是偶数，可以分解为两个质数的和)欧拉在回信中也提出另一等价版本，即任一大于 2 的偶数都可写成两个质数之和。今日常见的猜想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过 $a$ 个的数与另一个素因子不超过 $b$ 个的数之和"记作" $a+b$"。1966年陈景润证明了 $1+2$ 成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。 今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。 从关于偶数的哥德巴赫猜想，可推出：任一大于 7 的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。2013 年 5 月，巴黎高等师范学院研究员哈洛德·贺欧夫各特发表了两篇论文，宣布彻底证明了弱哥德巴赫猜想。 那么，对于一个整数 $n$，求使得 $n=\sum k_ip_i\ |\ k_i\in \rm N^+$ 且 $p_i$ 为质数（即将 $n$ 分解成若干个质数之和）的方案总数。$\forall i\neq j\ \exist\ p_i\neq p_j$。

无

无

| Subtask 编号 | 分值 | $1\le n\le$ | $1\le t\le$ | 时间，空间 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1$(1\sim3)$ | 20 | 100 | 10 | $800\rm{ms},100\rm{MB}$ | | 2$(4\sim11)$ | 35 | 10000 | 5 | $1000\rm{ms},125\rm{MB}$ | | 3$(12\sim20)$ | 45 | 10000 | 10000 | $1000\rm{ms},128\rm{MB}$ | 对于 $20\%$ 的数据，$1\le n\le 100$； 对于全部测试点，$1\le n\le 10,000$，$1\le t\le 10$。