【題解】ZeroJudge d188: 11342 – Three-square

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d188
【解題想法】建表

  • 由小到大枚舉所有 {i, j, k}, i^2 + j^2 + k^2 <= 50000
  • 建表 mp[i^2 + j^2 + k^2] = {i, j, k}
#include <iostream>
#include <vector>
#include <map>
using namespace std;
map <int, vector<int> > mp;
 
int main() {
    for (int i = 0; i < 225; i++){
        if (i * i > 50000) break;
        for (int j = 0; j < 225; j++){
            if (i * i + j * j > 50000) break;
            for (int k = 0; k < 225; k++){
                int n = i * i + j * j + k * k;
                if (n > 50000) break;
                if (mp.count(n)) continue;
                mp[n] = {i, j, k};
            }
        }
    }
    int N, K;
    cin >> N;
    while (N--){
        cin >> K;
        if (mp.count(K)){
            for (auto i: mp[K]){
                cout << i << " ";
            }
            cout << "\n";
        } else {
            cout << "-1\n";
        }
    }
}
分享本文 Share with friends