#UVa:11342-Three-square

灆洢 2014-12-23 17:55:58

這題用建表法紀錄答案即可。建表方式像質數篩法那樣,將aa+bb+c*c的那格填入答案。

C++(0.195)

/*******************************************************/
/* UVa 11342 Three-square                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/12/23                                 */
/*******************************************************/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <string>
using namespace std;

string to_string( int value ){
  string str;
  stringstream ss(str);
  ss << value;
  return ss.str();
}

int main(){
  string threeSquareOutput[50005];
  for( int i = 0 ; i <= 50000 ; ++i ){
    threeSquareOutput[i] = "-1";
  }

  for( int i = 0 ; i <= 500 ; ++i ){
    for( int j = i ; j <= 500 ; ++j ){
      for( int k = j ; k <= 500 ; ++k ){
        int n = i*i + j*j + k*k;
        if( n > 50000 ) break;
        if(threeSquareOutput[n][0] == '-'){
          threeSquareOutput[n] = to_string(i) + ' ' + to_string(j) + ' ' + to_string(k);
        }
      }
    }
  }

  int N;
  while( scanf("%d", &N) != EOF ){
    int K;
    for( int i = 0 ; i < N ; ++i ){
      scanf("%d", &K);
      printf("%s\n", threeSquareOutput[K].c_str());
    }
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料