PKU 1840 Eqs
http://poj.org/problem?id=1840
与えられた係数を持つ三次方程式の解の個数を求めろというような問題。
3個と2個に分けてやる。
mapを使ったらTLEだったのでハッシュ書きました。
typedef struct _node{ int key; int val; _node*next; }node; const int MOD=100007; node*hash[MOD]; node ent[1000000]; int sz; void insert(int in){ int ha=(in%MOD+MOD)%MOD; for(node*p=hash[ha];p;p=p->next){ if(p->key==in){ p->val+=1; return; } } node*p=hash[ha]; hash[ha]=ent+sz++; hash[ha]->next=p; hash[ha]->key=in; hash[ha]->val=1; } int get(int in){ int ha=(in%MOD+MOD)%MOD; for(node*p=hash[ha];p;p=p->next){ if(p->key==in) return p->val; } return 0; } int a[5]; main(){ rep(i,5)cin>>a[i]; for(int x1=-50;x1<=50;x1++){ if(x1==0)continue; int x13=x1*x1*x1; for(int x2=-50;x2<=50;x2++){ if(x2==0)continue; insert(a[0]*x13+a[1]*x2*x2*x2); } } int ans=0; for(int x3=-50;x3<=50;x3++){ if(x3==0)continue; int x33=x3*x3*x3; for(int x4=-50;x4<=50;x4++){ if(x4==0)continue; int x43=x4*x4*x4; for(int x5=-50;x5<=50;x5++){ if(x5==0)continue; ans+=get(a[2]*x33+a[3]*x43+a[4]*x5*x5*x5); } } } cout<<ans<<endl; }