题目连接:http://59.69.128.200/JudgeOnline/problem.php?pid=136
题目:有以下等式:a1*x13+a2*x23+a3*x33+a4*x43+a5*x53=0
x1,x2,x3,x4,x5都就在区间[-50,50]之间的整数,且x1,x2,x3,x4,x5都不等于0.
问:给定a1,a2,a3,a4,a5的情况下,x1,x2,x3,x4,x5共有多少种可能的取值?
解题报告:可以将a1*x13+a2*x23+a3*x33+a4*x43+a5*x53=0分解成a1*x13+a2*x23=-(a3*x33+a4*x43+a5*x53);
由于a1*x13+a2*x23比较大,如果用数组来保存的内存会超,所以可以采用哈希来解决。
#include<iostream> #include<algorithm> using namespace std; struct A {int x,y;A *next;}; A *s[100000]; int a=2*50*50*50*50; int main() { int n;cin>>n; while(n--) { for(int i=0;i<100000;i++){ s[i]=new A;s[i]->next=NULL; } int x1,x2,x3,x4,x5;cin>>x1>>x2>>x3>>x4>>x5; long long m=0;long long sum=0; for(int i=-50;i<=50;i++){ if(i==0)continue; for(int j=-50;j<=50;j++){ if(j==0)continue; sum=x1*i*i*i+x2*j*j*j;m=sum>=0?sum:-sum; A *p;A *r=new A;m%=100000;p=s[m]->next;int flat=0; while(p){ if(p->x==sum){p->y++;flat=1;break;} else p=p->next; } if(!flat) { r->x=sum;r->y=1;r->next=s[m]->next;s[m]->next=r; } } } int t=0; for(int i=-50;i<=50;i++){ if(i==0)continue; for(int j=-50;j<=50;j++){ if(j==0)continue; for(int k=-50;k<=50;k++){ if(k==0)continue; sum=x3*i*i*i+x4*j*j*j+x5*k*k*k;A *p; m=sum>=0?sum:-sum;if(m>a)continue; m%=100000;p=s[m]->next; while(p) { if(p->x==sum){t+=p->y;break;} else p=p->next; } } } } cout<<t<<endl; } }