Question

NOIP2009普及组复赛解题报告 急需！！！（软件类型：C++ !!! )2天之内回答正确的追加！！

Answer 1

Problem 1: poly 多项式输出

【分析】

简单的字符串处理题目，注意处理系数为-1,1,0的项，以及多项式的一次项不需给出次数（注意：样例中并没有带一次项的数据）.故而只需分类讨论n,2..n-1,1,0项即可.

Problem 2: score 分数线划定

【分析】
本题和NOIP 2007的奖学金思路一致，同样是简单的排序题目.考虑到n<=5000，故而直接使用冒泡排序即可.当然，为了保险起见使用快速排序也未尝不可.

Problem 3: cell 细胞分裂

【分析】

仔细读题后可以发现，本题的实质就是求 中t的最小值.这样一来，我们可以直接使用高精度算法来枚举t的最小值.但高精度算法却不能处理任何细胞都不满足要求的情况.故而，我们需要进行简单的数学分析.
通过观察得知，如果i细胞可以满足情况时，那么 有的质因数， 也一定有.反之，若 有的质因数，没有，则i细胞不能满足情况.而 的充要条件就是 中质因数的次数大于等于 中相同的质因数的次数.至此，题意分析完毕.

接下来，我简单的说一下算法的实现过程：

（1） 构造一个1..30000的质数表，来分解质因数.

（2） 注意 的特殊情况，此时任何 都能整除 ，故而直接输出0.

（3） 分解 ，建立一个m数组储存分解结果.

（4） 分解 ,然后递增t，直到 .这里有个优化，其实分解 时只需处理 中有的质因数，同样，枚举t的时候也只需处理 中有的质因数.此外，还需要设置一个变量处理 中的质因数>30000的情况，一种较为简单的方法是对比每次 的值，连续两次相等则退出.

（5） 输出最终结果.
第四题我也不知道。

Answer 2

唔…………进错房间了，俺是Pascal的