cuadrados dobles: contar números que son sumas de dos cuadrados perfectos

Question

Fuente: Facebook Hacker CupQualification Round 2011

Un número de doble cuadrado es un número entero X que se puede expresar como la suma de dos cuadrados perfectos. Por ejemplo, 10 es un cuadrado doble porque 10 = 3 + 1 . Dado X, ¿cómo podemos determinar la cantidad de formas en que puede escribirse como la suma de dos cuadrados? Por ejemplo, 10 sólo se puede escribir como 3 + 1 (no contamos 1 + 3 como diferente). Por otra parte, 25 se puede escribir como 5 + 0 o como 4 + 3 .

Debe resolver este problema para 0 ≤ X ≤ 2,147,483,647.

Ejemplos:

• 10 => 1
• 25 => 2
• 3 => 0
• 0 => 1
• 1 => 1

Answer 1

Factor el número n, y comprobar si tiene una factor primo p con valoración impar, tal que p = 3 (mod 4). Lo hace si y solo si n no es una suma de dos cuadrados.

El número de soluciones tiene una expresión de formulario cerrado que implica el número de divisores de n. Ver this, Theorem 3 para una declaración precisa.

Answer 2

El bucle a través de todos los pares (a, b) es inviable debido a las limitaciones de X. Sin embargo, ¡hay una manera más rápida!

Para el fijo a, podemos calcular b: b = √ (X - a). b no siempre será un número entero, así que tenemos que verificar esto. Debido a problemas de precisión, realice la verificación con una tolerancia pequeña: si b es x.99999, podemos estar bastante seguros de que es un número entero. Entonces recorremos todos los valores posibles de a y contamos todos los casos donde b es un entero. Tenemos que tener cuidado de no contar dos veces, por lo que colocamos la restricción de que < = b. Para X = a + b , a será como máximo √ (X/2) con esta restricción.

Aquí es una implementación de este algoritmo en C++:

int count = 0; 
// add EPS to avoid flooring x.99999 to x 
for (int a = 0; a <= sqrt(X/2) + EPS; a++) { 
    int b2 = X - a*a; // b^2 
    int b = (int) (sqrt(b2) + EPS); 
    if (abs(b - sqrt(b2)) < EPS) // check b is an integer 
     count++; 
} 
cout << count << endl; 

See it on ideone with sample input

Answer 3

Aquí es una solución mucho más simple:

create list of squares in the given range (that's 46340 values for the example given) 

for each square value x 
    if list contains a value y such that x + y = target value (i.e. does [target - x] exist in list) 
    output √x, √y as solution (roots can be stored in a std::map lookup created in the first step) 

Answer 4

Tenía prisa, así que lo resolví usando un enfoque más bien de fuerza bruta (muy similar al de Marcog) usando Python 2.6.

def is_perfect_square(x): 
    rt = int(math.sqrt(x)) 
    return rt*rt == x 

def double_sqaures(n): 
    rng = int(math.sqrt(n)) 
    ways = 0 
    for i in xrange(rng+1): 
     if is_perfect_square(n - i*i): 
      ways +=1 
    if ways % 2 == 0: 
     ways = ways // 2 
    else: 
     ways = ways // 2 + 1 
    return ways 

Nota: ways será par cuando el número es un sqaure perfecto.

Answer 5

El número de soluciones (x, y) de

x^2 + y^2 = n

sobre los números enteros es exactamente 4 veces el número de divisores de n congruente con 1 mod 4. existen identidades similares también para los problemas

x^2 + 2y^2 = n

y

x^2 + y^2 + z^2 + w^2 = n.

Answer 6

Aquí es mi respuesta simple en O(sqrt(n)) complejidad

x^2 + y^2 = n 
x^2 = n-y^2 
x = sqrt(n - y^2) 

x deben estar entero por lo (n-y^2) debe ser cuadrado perfecto. Loop a y=[0, sqrt(n)] y comprobar si (n-y^2) es cuadrado perfecto o no

Pseudocódigo:

count = 0; 
for y in range(0, sqrt(n)) 
    if(isPerfectSquare(n - y^2)) 
     count++ 
return count/2 

Answer 7

Aquí hay una versión que es trivialmente O (sqrt (N)) y evita todas las ramas de bucle interno.

Comience por generar todos los cuadrados hasta el límite, fácilmente sin multiplicaciones, luego inicialice un índice ly r.

En cada iteración calcula la suma, luego actualice los dos índices y el recuento basándose en una comparación con el valor objetivo. Esto es iteraciones sqrt (N) para generar la tabla y las iteraciones sqrt (N) máximas del bucle de búsqueda. El tiempo de ejecución estimado con un compilador razonable es de 10 ciclos de reloj por sqrt (N), por lo que para un valor de entrada máximo si 2^31 (sqrt (N) ~ = 46341) esto debería corresponder a menos de 500K ciclos de reloj o algunas décimas de un segundo:

unsigned countPairs(unsigned n) 
{ 
    unsigned sq = 0, i; 
    unsigned square[65536]; 

    for (i = 0; sq <= n; i++) { 
     square[i] = sq; 
     sq += i+i+1; 
    } 

    unsigned l = 0, r = i-1, count = 0; 

    do { 
     unsigned sum = square[l] + square[r]; 
     l += sum <= n;  // Increment l if the sum is <= N 
     count += sum == n; // Increment the count if a match 
     r -= sum >= n;  // Decrement r if the sum is >= N 
    } while (l <= r); 
    return count; 
} 

un buen compilador puede observar que los tres compara al final están todos usando los mismos operandos por lo que sólo necesita un único código de operación CMP seguido de tres operaciones condicionales movimiento diferente (CMOVcc).