PKU 1840-Eqs

問題概要

a₁x₁³+a₂x₂³+a₃x₃³+a₄x₄³+a₅x₅³=0
を満たすような整数x1,x2,x3,x4,x5を全て求め，その種類の個数を答えよ

解法

x4,x5とx1,x2,x3についてそれぞれ列挙する．
計算量が50^3になり間に合う．

実装(C++)

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int a[5];
short count[6250000*6];
const int CMT=6250000*6/2;
int main() {
	for(int i=0;i<5;i++)cin>>a[i];
	//後ろ2つの列挙
	for(int x4=-50;x4<=50;x4++){
		for(int x5=-50;x5<=50;x5++){
			if(x4==0)continue;
			if(x5==0)continue;
			count[x4*x4*x4*a[3]+a[4]*x5*x5*x5+CMT]+=1;
		}
	}
	int res=0;
	for(int x1=-50;x1<=50;x1++){
		for(int x2=-50;x2<=50;x2++){
			for(int x3=-50;x3<=50;x3++){
				if(x2==0)continue;
				if(x1==0)continue;
				if(x3==0)continue;
				res+=count[-(a[0]*x1*x1*x1+a[1]*x2*x2*x2+a[2]*x3*x3*x3)+CMT];
			}
		}
	}
	cout<<res<<endl;
	return 0;
}