[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Res: [obm-l] Algoritmo
O algoritmo que usei para achar soluções enormes (escrevi em C) foi basicamente desse jeito:
1) Descubra todos os números possíveis com b positivo (ou seja, para cada a com a²<1000, teste os b's). Essa parte é muito simples e rápida.
2) Achar os números com b negativo:
- Volte o a para 0 (importante, porque há soluções com a²<1000 e b<0), e comece a diminuir o b (começando de -1). Eu escolhi ir diminuindo o "b" e não o "a" porque tem menos b's do que a's em qualquer solução.
- Para um determinado "b", todos os possíveis "a" são dados pela inequação:
100<a^2 + b^3<999
100-b^3<a^2<999-b^3
sqrt(100-b^3) < a < sqrt(999-b^3)
Se não há números inteiros entre sqrt(100-b^3) e sqrt(999-b^3), então não há solução. Se há, esses números são soluções garantidas, e você pode fazer o que quiser com eles (mostrar na command line, adicionar a uma lista de soluções, etc.). O código está aí embaixo, mas se você não souber usar GMP não vai servir pra muita coisa... O último valor que eu vejo depois de meio minuto rodando ele é:
a = 611085363
b = -720114
a^2+b^3 = 225
Depois desse valor ele parece parar de produzir soluções por um bom tempo.
#include <stdio.h>
#include "gmp.h"
int main() {
mpz_t b, a, b_cbd, min_val, max_val, sum, a_sq;
mpz_init_set_si(b, -1);
mpz_init(a);
mpz_init(b_cbd);
mpz_init(min_val);
mpz_init(max_val);
mpz_init(sum);
mpz_init(a_sq);
while (1) {
mpz_pow_ui(b_cbd, b, 3);
mpz_ui_sub(min_val, 100, b_cbd);
if (mpz_perfect_square_p(min_val)) {
mpz_sqrt(min_val, min_val);
}
else {
mpz_sqrt(min_val, min_val);
mpz_add_ui(min_val, min_val, 1);
}
mpz_ui_sub(max_val, 999, b_cbd);
mpz_sqrt(max_val, max_val);
mpz_add_ui(max_val, max_val, 1);
mpz_set(a, min_val);
while (mpz_cmp(a, max_val) == -1) {
mpz_pow_ui(a_sq, a, 2);
mpz_add(sum, b_cbd, a_sq);
mpz_out_str(NULL, 10, sum);
printf(" ");
mpz_out_str(NULL, 10, a);
printf(" ");
mpz_out_str(NULL, 10, b);
printf("\n");
mpz_add_ui(a, a, 1);
}
mpz_sub_ui(b, b, 1);
}
}
Quem te passou esse problema disse que ele podia ser resolvido? Ou você está satisfazendo um "problema-curiosidade"? Se for a segunda opção, é possível que você nunca encontre todos os valores possíveis. Se for a primeira, talvez tenha um jeito matemático de reduzir os possíveis valores finais...