问题描述

　　已知一个n元高次方程：
　　　　　　　　　　　　
　　其中：是未知数，是系数，是指数。且方程中的所有数均为整数。
　　假设未知数求这个方程的整数解的个数。

输入文件（equation.in）
　　文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示和。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

输出文件（equation.out）
　　文件仅一行，包含一个整数，表示方程的整数解的个数。

输入样例
3
150
1 　2
-1　2
1 　2

输出样例
178

约束条件
　　
　　
　　方程的整数解的个数小于。
　　★本题中，指数Pi(i=1,2,……,n)均为正整数。

《方程的解数》解题报告

福州一中 林尔桢

【问题简述】

　　一个给定各项系数、指数的N元高次方程（其中n<=6）
　　　　　　
　　已知方程中的所有数均为整数，求这个方程的解的个数(解的取值小于M，其中M小于150)。

【问题分析】

　　本题无法得到某种有效的数学方法，只能用搜索解决。

　　最简单的一种方法就是从X1到Xn，逐个地搜其的范围，搜到第n个数时统计所求得的和，当和为0时将求得的解的个数加1。这种方法从理论上可以得到最优解，当我们看一看算法的复杂度：O(M^N)，当N、M的取值均为最大时，要搜150^6＝11390625000000次，显然，这样的速度是我们无法忍受的，需要在这个算法的基础上进行优化。

　　不难发现，在搜索X1至Xn的时侯只需从X1搜到X(n-1)，因为Xn的取值可以根据前n-1项得到--当Xn取值为整数并在题目给定的区间内时，就得到一个解。这个改进使算法时间复杂度缩小的原先的1／150，速度得到很大的提高，但对于最大数据仍须搜150^5＝75937500000次，仍然达不到要求，算法还需进一步改进。

　　回顾一下优化过程，我们是把方程中的最后一个数移到了方程的右边，以求加快速度。那么，我们大胆的设想：能否将方程项数的一半移到右边？答案是肯定的：先将方程左边的（n+1） div 2项移到右边（同时改变符号），再分别算出此时方程左右两边的所有取值--这里要用好的排序算法（如qsort）以节省时间--左右相等的取值数目即为方程的解数。

　　按照上述方法，当N、M取值最大时，算出方程左右取值需搜索2×(150^3)=6750000次，而qsort的算法复杂度为2×O(3375000×log23375000)，可以接受。此时，查找的算法决定了整个程序的优劣：若用普通查找的再搜3375000×3375000次，前功尽弃；而用二分查找复杂度为O(3375000×log23375000)。这样定下来的算法效率大为提高。

【进一步优化】

　　为了进一步提高程序效率，可对程序进行改进如下：

　　1．预处理：开一［1..6,1..150］数组存贮方程中每一项当自变量取1至150时的得数，以免以后重复计算。
　　2．在排序后对得到的left、right数组进行处理，即将它们缩小至left[1]=right[1]且left[tl]=right[tr]（tl、tr分别为left、right中数的个数），可以减少二分查找时的运算量。

　　经过以上分析、优化，我们可以得出本题的数据结构及算法流程：

【数据结构】
Const
　Maxn=3375000;
Var
　left,right:array[1..maxn] of longint; {分别记录方程左右两边的解}
　t:longint;　　　　　　　　　　　　　　　{计数器，记录已得到的解数}

【算法流程】
　　1. 读入数据；
　　2. 预处理；
　　3. 建立方程（即将得到的各项结果分两堆相加分别存入left、right数组中）；
　　4. 对left、right数组分别进行qsort；
　　5. 二分查找
　　6. 打印

【不足】

　　程序运行时的绝大多数时间花在快速排序上，而当N、M取极大值时，排序要消耗大量时间。

【总结】

　　此题对选手分析、判断、优化搜索的能力有着很高的要求，看来，平时这类能力的培养，是至关重要的。