题目描述 Description
已知一个n元高次方程：
k1x1p1+k2x2p2+……+knxnpn = 0
其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。
假设未知数1≤ xi ≤M, i=1,,,n，求这个方程的整数解的个数。
输入描述 Input Description
文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。
输出描述 Output Description
文件仅一行，包含一个整数，表示方程的整数解的个数。
样例输入 Sample Input
3
150
1 2
-1 2
1 2
样例输出 Sample Output
178
数据范围及提示 Data Size & Hint
1≤n≤6；1≤M≤150；
|k1Mp1|+|k2Mp2|+……+|knMpn |< 231
方程的整数解的个数小于231。
★本题中，指数Pi(i=1,2,……,n)均为正整数。
练一下meet in the middle
暴力搜索：150 ^ 6 =11390625000000
meet in the middle :150 ^3 =3375000
计算满足 a+b+c+d+e+f=0 的数的个数
可以算 （a+b+c）+ （d+e+f） = 0
dfs两次，每次dfs一半
结果用双指针逼近法、乘法原理 O（n） 处理
#include<cstdio> #include<algorithm> #include<iostream> #define N 3875000 using namespace std; int n,m,half,nod,ans; int k[10],p[10]; int tmp1[N+1],sum1,tmp2[N+1],sum2; int qm(int a,int q) { int b=1; for(;q;a*=a,q>>=1) if(q & 1) b*=a; return b; } void dfs(int now,int tot,int *tmp,int & sum) { if(now>nod) { tmp[++sum]=tot; return; } for(int i=1;i<=m;i++) dfs(now+1,tot+k[now]*qm(i,p[now]),tmp,sum); } void work() { int cnt1,cnt2,j=sum2; sort(tmp1+1,tmp1+sum1+1); sort(tmp2+1,tmp2+sum2+1); for(int i=1;i<=sum1;i++) { while(j && tmp1[i]+tmp2[j]>0) --j; if(!j) break; if(!(tmp1[i]+tmp2[j])) { cnt1=1,cnt2=1; while(i<sum1 && tmp1[i+1]==tmp1[i]) cnt1++,i++; while(j>1 && tmp2[j-1]==tmp2[j]) cnt2++,j--; ans+=cnt1*cnt2; } } } int main() { freopen("equation1.in","r",stdin); freopen("equation1.out","w",stdout); scanf("%d%d",&n,&m); half=n>>1; for(int i=1;i<=n;i++) scanf("%d%d",&k[i],&p[i]); nod=half; dfs(1,0,tmp1,sum1); nod=n; dfs(half+1,0,tmp2,sum2); work(); printf("%d",ans); }