方程的解数
问题描述
已知一个n元高次方程：
其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。
假设未知数1≤ xi ≤M, i=1,,,n，求这个方程的整数解的个数。
输入文件（equation.in）
文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。
输出文件（equation.out）
文件仅一行，包含一个整数，表示方程的整数解的个数。
输入样例
3
150
1 2
-1 2
1 2
输出样例
178
约束条件
1<=n<=6,1<=M<=150;
方程的整数解的个数小于231。
★本题中，指数Pi(i=1,2,……,n)均为正整数。
下面我们来仔细分析下面这个问题：
题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且我们注意到解的范围最多150个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M^6).,这个复杂度是无法承受的.看来只有另辟蹊径了.
因此需要寻找更好的方法，自然想到能否缩小枚举的范围呢？
可以仅仅通过枚举3个未知数的值来找到答案,这样一来, 前一半式子的和值 S 可以确定，这时只要枚举后3 个数的值，检查他们的和是否等于 -S 即可。这样只相当于在 O(M^3) 前面加了一个系数，当然还需要预先算出 1 到 150 的各个幂次的值.
想到了这里，问题就是如何迅速的找到某个 S 是否曾经出现过，以及出现过了多少次，于是就变成了"某个元素是否在给定集合中"这个问题,所以我们选择用使用哈希表解决这个问题。哈希函数的构造我们采用除余法:,即 h(k ) = k mod p,这里p我们选择一个大素数4000037.
程序中mid变量=n/2,首先枚举前n/2的和值S,并将S值保存在哈希表中,我们不仅要记录S的值,同时我们还用一个数组amount[]记录某个S值出现的次数.然后计算多项式后n/2项的和的相反数,再在哈希表中寻找是否有与之相等的S值,若相等则将相等的S值对应的amount[]值相加,就是答案.
#include<iostream>
#include<cstdlib>#include<cmath>#define max 4000037 //哈希函数中的大素数 using namespace std;long answer[max],amount[max],use[max];//answer[i]是哈希表,amount[i]表示 s出现的次数,use[i]表示哈希表中该位置不位空 long mid;long k[6],p[6];//k[i]是各项的系数,p[i]是各项的指数 long n,m,total;//n,m是题目中的约束条件,total是结果 long locate(long s)//哈希表的定位函数 { long h;h=s;while (h<0) h+=max;while (h>=max) h-=max;while (use[h] && answer[h]!=s){ h++;if (h>=max) h-=max;} return h; } void insert(long s)//哈希表的插入函数 { long posi=locate(s);if (!use[posi]) { use[posi]=1;answer[posi]=s; }amount[posi]++;} void firsthalf(long d,long s)//计算多项式前n/2项的和,保存在哈希表中 { if (d==mid){ insert(s);return;}long t;for (long i=1; i<=m; i++){ t=k[d];if (t!=0 && i!=1){ for (long j=0; j<p[d]; j++) t*=i;}firsthalf(d+1,t+s);}}void find(long d,long s)//计算多项式后n/2项的和的相反数,并判断是否和前n/2项相等 { if (d==n){ long posi;s=-s;posi=locate(s);if (answer[posi]==s)total+=amount[posi];return;}long t;for (long i=1; i<=m; i++){ t=k[d];if (t!=0 && i!=1){ for (long j=0; j<p[d]; j++)t*=i;}find(d+1,t+s);}} int main(){ freopen("dat.in","r",stdin);freopen("dat.out","w",stdout);cin>>n>>m;for (long i=0; i<n; i++)cin>>k[i]>>p[i];mid=n/2;firsthalf(0,0);find(mid,0);cout<<total<<endl;return 0;
}