URI (BEECROWD) - 1558 - Soma de Dois Quadrados - Ad-Hoc - C e C++

Vamos de mais um problema Ad-hoc por aqui! Este problema também poderia ser classificado na categoria Matemática, mas na plataforma Beecrowd consta como Ad-hoc. O título do problema é "Soma de Dois Quadrados". Confira a solução em C e C++ e conte nos comentários se está muito diferente da sua solução.

Um grande abraço!

Plataforma: URI (BEECROWD)

Problema: 1558

Enunciado:

Quais números inteiros podem ser representados por uma soma de dois inteiros ao quadrado?

É essa a pergunta que seu programa deve responder!

Por exemplo, o número 41 pode ser representado como (-4)2 + 52 = 41, já o número 7 não pode ser representado da mesma maneira.

Linguagens: C e C++

Solução:

A estratégia aqui foi, após ler n, obter a raiz de n. Por que isso? Assim garantimos que não vamos percorrer valores inutilmente, pois o maior valor que, ao quadrado, pode igualar n é raiz de n. Sabendo disso, preenchi um array com o quadrado de todos os números até raiz de n. Depois, iterei com dois laços de repetição para testar se entre os valores do meu array havia alguma combinação que somasse dois valores e chegasse no valor de n. Se isso acontecesse, sim, é possível e a resposta deve ser YES, senão, imprime NO.

Código em C:

#include <stdio.h>
#include <math.h>
int main() {
    
    int n;
    
    while (scanf("%d", &n) != EOF) {
        int raiz = sqrt(n);
        int resposta = 0;
        int raizes[raiz];
        int tam = raiz;
        int i;
        int j;
        if (n >= 0) {
            while (raiz != -1) {
                raizes[raiz] = raiz * raiz;
                raiz--;
            }
            for (i = 0; i <= tam; i++)
                for (j = 0; j <= tam; j++)
                    if (n == raizes[i] + raizes[j]) {
                        resposta = 1;
                        break;
                    }
            
        }
        printf("%s\n", (resposta? "YES" : "NO"));
    }
    
    return 0;
}

Código em C++:

Esta solução segue a lógica explicada anteriormente, a única diferença é que não utilizei o array no estilo C, mas sim a estrutura vector e suas funções: de acesso por índice - at(), de obter o tamanho - size() e de inserir valor - push_back.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    
    int n, raiz;
    
    while (cin >> n) {
        raiz = sqrt(n);
        vector<int> raizes;
        bool resposta = false;
        if (n >= 0) {
            while (raiz != -1) {
                raizes.push_back(raiz * raiz);
                raiz--;
            }
            for (int i = 0; i < raizes.size(); i++)
                for (int j = 0; j < raizes.size(); j++)
                    if (n == raizes.at(i) + raizes.at(j)) {
                        resposta = true;
                        break;
                    }
            
        }
        cout << (resposta? "YES" : "NO") << endl;
    }
    
    return 0;
}