# 1558 - Soma de Dois Quadrados

## Descrição

{% embed url="<https://www.urionlinejudge.com.br/judge/pt/problems/view/1558>" %}

## Solução

Como nosso número terá sempre um módulo menor ou igual a 10000 e sabemos que 100² = 10000, então é bem possível apenas guardar primeiramente todas as possibilidades de somar de quadrado entre os números 1 e 100 e depois apenas perguntar se o número pedido apareceu em alguma dessas possibilidades ou não.

Para representar as somas, basta fazermos primeiro um looping para guardar todos os números entre 1 e 100 elevado ao quadrado e depois dois looping aninhados para guardar todas as somas possíveis entre os números ao quadrado. Se não pudermos usar um conjunto, podemos usar um vetor, apenas tomando cuidado para a somar não ultrapassar 10000 (ou colocar um limite maior de 20000).

{% tabs %}
{% tab title="C99" %}

```c
#include <string.h>
#include <stdio.h>

int resposta[20001];

void preProcessa(){
    memset(resposta, 0, sizeof(resposta));

    for(int i = 0; i < 101; ++i){
        resposta[i * i] = 1;
    }

    for(int i = 1; i < 101; ++i){
        for(int j = i; j < 101; ++j){
            resposta[i * i + j * j] = 1;
        }
    }
}

int main(){
    int numero;

    preProcessa();

    while(scanf("%d", &numero) != EOF){
        if(numero < 0)  printf("NO\n");
        else            printf("%s\n", resposta[numero] ? "YES" : "NO");
    }

    return 0;
}
```

{% endtab %}

{% tab title="C++17" %}

```cpp
#include <iostream>
#include <set>

using namespace std;

set<int> respostas;

void preProcessa(){
    for(int i = 0; i < 101; ++i){
        respostas.insert(i * i);
    }

    for(int i = 1; i < 101; ++i){
        for(int j = i; j < 101; ++j){
            respostas.insert(i * i + j * j);
        }
    }
}

int main(){
    int numero;

    preProcessa();

    while(cin >> numero){
        cout << (string) (respostas.count(numero) ? "YES" : "NO") << endl;
    }

    return 0;
}
```

{% endtab %}

{% tab title="JavaScript 12.18" %}

```javascript
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.trim().split('\n');

let respostas = new Set();

const preProcessa = () => {
    for(let i = 0; i < 101; ++i){
        respostas.add(i * i);
    }

    for(let i = 1; i < 101; ++i){
        for(let j = i; j < 101; ++j){
            respostas.add(i * i + j * j);
        }
    }
};

preProcessa();

while(lines.length){
    let numero = parseInt(lines.shift().trim());

    console.log(respostas.has(numero) ? "YES" : "NO");
}
```

{% endtab %}

{% tab title="Python 3.9" %}

```python
respostas = set()

def preProcessa():
    for i in range(101):
        respostas.add(i * i)
    
    for i in range(1, 101):
        for j in range(i, 101):
            respostas.add(i * i + j * j)

preProcessa()

while True:
    try:
        numero = int(input().strip())

        print("YES" if numero in respostas else "NO")
    except EOFError:
        break
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xtecna.gitbook.io/solucoes-da-beecrowd/ad-hoc/1558-soma-de-dois-quadrados.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.