1484 - 다이어트

https://www.acmicpc.net/problem/1484

현재 몸무게를 a, 기억하는 예전 몸무게를 b라 했을 때 $a^2 - b^2 = G$ 가 되는 모든 a를 출력한다.

$1^2$ 부터 $10000^2$ 를 모두 저장하고 $b^2 + G$ 가 되는 제곱꼴(= $a^2$)를 이진탐색으로 찾았다.

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int main(){
    vector<lld> squares;
    for(lld i=1; i<=100000; ++i) squares.push_back(i*i);
    int G;
    scanf("%d", &G);
    bool find = false;
    for(lld i=1; i<=100000; ++i){
        if(binary_search(squares.begin(), squares.end(), (i*i)+G)){
            printf("%lld\n", (lld)sqrt((i*i)+G));
            find = true;
        }
    }
    if(!find) puts("-1");
    return 0;
}