Buenas, tengo un problema que le dejaron a un amigo en su clase de programacion, y y que le piden que escriba en lenguaje C, usando solo funciones y punteros y arreglos :
Un programa que determine la cantidad de formas distintas
T en las que se puede escribir un numero entero
N como suma de dos potencias a^p + b^q donde a>=b>=1, p>=2 y q>=2. para la potencias de uno solo se considera 1^2, y piden que el numero este en un rango de [1, 1000].
ejem: 17=4^2+1^2=3^2+2^3 en este caso
T seria igual a 2.
Ya se me a ocurrido una idea, y es hacerlo a fuerza bruta, osea primero hallar los resultadoss de las potencias al cuadrado de numeros del 1 a la n en donde la potencia sea menor a 1000, y asi seguir hasta llegar a la potencia de 2 a la 10, en donde cada resultado de la potencia se guardaria en un arreglo, en total serian algo de 52 elementos del arreglo, y luego descomponer por sumas al numero N, en este caso las sumas totales serian N/2, y luego cada sumando se compararia a un elemento del arreglo, si ambos coinciden con alguno, entonces T incrementaria en uno, hasta comparar todas las posibilidades. calculando el numero total de posibilidades para el numero mayor que es 1000, serian de 1000/2=500 posibilidades que en donde cada sumando de N se compararia con un arreglo, 2*500*52=52000, pero veo que seria demasiadas comparaciones.
Si alguien encuentra una solucion sin tantas comparaciones, le estaria agradecido.
