1558 - Soma de Dois Quadrados
Pré-processar os resultados pode ser uma boa aqui!
Descrição
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).
#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;
}
Last updated
Was this helpful?