Sí.
1. La idea de la búsqueda binaria es la siguiente: imaginate que tenés n números $a_1<a_2<\cdots <a_n$ y te preguntan si un número, a, está en esa lista. Una cosa que podés hacer es recorrer la lista, viendo los números uno por uno y fijándote si alguno es a. Pero se puede hacer mejor. Suponete que $a < a_i$, para cierto i. Esto te dice que los números siguientes a $a_i$ no pueden ser a. Igualmente, si sabés que $a_i < a$ entonces sabés que a no está entre los números $a_1,\ldots,a_i$ de la lista, así que sólo tenés que mirar los que siguen.
Si queremos saber si a está en la lista $a_i < a_{i+1} < \cdots < a_j$, sea $k= \lfloor\frac{i+j+1}2\rfloor$ (o sea (i+j+1)/2 redondeado para abajo). Si $a=a_k$ lo encontramos. Si $a<a_k$ entonces seguimos buscando en la lista $a_i,\ldots,a_{k-1}$; si $a>a_k$ seguimos buscando en la lista $a_{k+1},\ldots,a_j$. Esto se implementa así:
int i = 0, j = CANT_DE_NUMEROS;
while( j - i >= 1 )
{
int k = (j+i)/2;
if( a[k] == A ) cout << "sí está" << endl;
else if( a[k] < A ) j = k;
else i = k+1;
}
cout << "no está" << endl;
Lo bueno de la búsqueda binaria es que es extraordinariamente rápida. Si la lista tiene $2^n$ números, la búsqueda binaria mira a lo sumo $n+1$.
En nuestro caso particular la lista es la de las potencias cuartas. Quizás podrías meter la búsqueda binaria adentro de tu código. Sin embargo, si estabas usando alguna función de librería para sacar raíz cuarta quizás no sea más rápido. No tengo idea. Yo no uso pow o sqrt porque no conozco su complejidad ni la cota de error (y porque no los necesito).
2. Sobre mirar los restos de los números en la división por ocho. Llamemos $r_k(n)$ al resto de dividir $n$ por $k$. Probablemente sepas que $r_k(a+b)=r_k(r_k(a)+r_k(b))$ y que $r_k(a\cdot b) = r_k( r_k(a) \cdot r_k(b) )$. Si un número $n$ es par entonces $r_8(n)$ puede ser 0, 2, 4 ó 6; si es impar, puede ser 1, 3, 5 ó 7. Haciendo las cuentas podés comprobar que $r_8(n^4)$ es cero, si n es par, y uno, si es impar. Ahora, si $a,b,c,d,e$ son enteros tales que $a^4+b^4+c^4+d^4=e^4$ entonces $r_8(a^4+b^4+c^4+d^4) = r_8(e^4)$. Si e es par entonces $r_8(e^4)=0$ así que $r_8(a^4+b^4+c^4+d^4)$ tiene que ser cero. Ahora los restos de $a^4,b^4,c^4,d^4$ son cero o uno, así que para que el resto de su suma sea cero, todos tienen que ser cero, es decir, todos tienen que ser pares (¿se ve?). Por otro lado, si e es impar, $r_8(e^4)=1$ así que $r_8(a^4+b^4+c^4+d^4)$ tiene que ser uno. De nuevo, los restos de $a^4,b^4,c^4,d^4$ son cero o uno, así que para que el resto de su suma sea uno, exactamente uno de ellos tiene que ser uno, es decir, uno tiene que ser impar y todos los demás pares.
Ahora supongamos que todos, a, b, c, d y e son pares y $a^4+b^4+c^4+d^4=e^4$. Entonces a/2, b/2, c/2, d/2 y e/2 también son enteros que cumplen esa ecuación, pero a/2 es menor que a, así que a esta solución la encontramos antes. De acá se sigue que sólo tenemos que buscar las soluciones con uno de los a,b,c,d impar y el resto par (¿se ve?).
Podríamos implementar esto así:
long long K = 600;
// primero a es impar, el resto par
for( long long a = 1; a < K; a += 2 )
for( long long a2 = a*a, a4 = a2*a2, b = a+1; b < K; b += 2 )
for( long long b2 = b*b, a4b4 = a4 + b2*b2, c = b; c < K; c += 2 )
for( long long c2 = c*c, a4b4c4 = a4b4 + c2*c2, d = c; d < K; d += 2 )
{
long lond d2 = d*d, e4 = a4b4c4 + d2*d2;
// chequear con búsqueda binaria si e4 es potencia cuarta
}
// ahora b es impar, el resto par
for( long long a = 2; a < K; a += 2 )
for( long long a2 = a*a, a4 = a2*a2, b = a+1; b < K; b += 2 )
for( long long b2 = b*b, a4b4 = a4 + b2*b2, c = b+1; c < K; c += 2 )
for( long long c2 = c*c, a4b4c4 = a4b4 + c2*c2, d = c; d < K; d += 2 )
{
long lond d2 = d*d, e4 = a4b4c4 + d2*d2;
// chequear con búsqueda binaria si e4 es potencia cuarta
}
// ahora c es impar, el resto par
for( long long a = 2; a < K; a += 2 )
for( long long a2 = a*a, a4 = a2*a2, b = a; b < K; b += 2 )
for( long long b2 = b*b, a4b4 = a4 + b2*b2, c = b+1; c < K; c += 2 )
for( long long c2 = c*c, a4b4c4 = a4b4 + c2*c2, d = c+1; d < K; d += 2 )
{
long lond d2 = d*d, e4 = a4b4c4 + d2*d2;
// chequear con búsqueda binaria si e4 es potencia cuarta
}
// ahora d es impar, el resto par
for( long long a = 2; a < K; a += 2 )
for( long long a2 = a*a, a4 = a2*a2, b = a; b < K; b += 2 )
for( long long b2 = b*b, a4b4 = a4 + b2*b2, c = b; c < K; c += 2 )
for( long long c2 = c*c, a4b4c4 = a4b4 + c2*c2, d = c+1; d < K; d += 2 )
{
long lond d2 = d*d, e4 = a4b4c4 + d2*d2;
// chequear con búsqueda binaria si e4 es potencia cuarta
}
Con esto el programa debería andar algo así como cuatro veces más rápido. Igual no es mucho mejor y es más feo para programar, pero bueno, si no el problema no tiene nada de matemática.
