PKU : 1840 - Eqs

問題概要

http://poj.org/problem?id=1840
問題文に書かれた式を満たすような, xの組み合わせ数を答えよ.

アルゴリズム

DPでやろうと思ったのですが, 値が大きすぎるため断念.
左2つと, 右3つに分割して計算し, 答えを併合しました.
C++では, mapではだめで, ハッシュを使わないといけないみたいです.

プログラム

public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  int[] t = new int[5];

  for(int i=0;i<5;i++){
    t[i] = sc.nextInt();
  }

  HashMap<Integer,Integer> left = new HashMap<Integer,Integer>();

  for(int i=-50;i<=50;i++){
    if(i == 0) continue;
    for(int j=-50;j<=50;j++){
      if(j == 0) continue;
      int cal = t[0]*i*i*i + t[1]*j*j*j;
      Integer tmp = left.get(cal);
      if(tmp == null){
        left.put(cal,1);
      }
      else{
        left.put(cal,tmp+1);
      }
    }
  }

  int res = 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;
        int cal = t[2]*i*i*i + t[3]*j*j*j + t[4]*k*k*k;
        Integer tmp = left.get(cal);
        if(tmp != null){
          res += tmp;
        }
      }
    }
  }

  System.out.println(res);
}