Tarea

Dados dos enteros dy n, encuentre el número de formas de expresar ncomo una suma de dcuadrados. Es decir, n == r_1 ^2 + r_2 ^2 + ... + r_d ^2tal que r_mes un entero para todos los enteros 1 ≤ m ≤ d. Tenga en cuenta que intercambiar dos valores diferentes (por ejemplo, r_1y r_2) se considera diferente de la solución original.

Por ejemplo, el número 45 se puede escribir como una suma de 2 cuadrados 8 formas diferentes:

45
== (-6)^2 + (-3)^2
== (-6)^2 + 3^2
== (-3)^2 + (-6)^2
== (-3)^2 + 6^2
== 3^2 + (-6)^2
== 3^2 + 6^2
== 6^2 + (-3)^2
== 6^2 + 3^2

Reglas

• Las soluciones integradas están permitidas pero no son competitivas (ejem, Mathematica )
• Las lagunas estándar también están prohibidas.
• Las entradas pueden invertirse.

Ejemplo de E / S

In:   d, n

In:   1, 0
Out:  1

In:   1, 2
Out:  0

In:   2, 2
Out:  4

In:   2, 45
Out:  8

In:   3, 17
Out:  48

In:   4, 1000
Out:  3744

In:   5, 404
Out:  71440

In:   11, 20
Out:  7217144

In:   22, 333
Out:  1357996551483704981475000

Este es el código de golf , por lo que las presentaciones que utilizan la menor cantidad de bytes ganan.

Python 3 , 125 bytes

n,d=eval(input())
W=[1]+[0]*n
exec("W=[sum(-~(j>0)*W[i-j*j]for j in range(int(i**.5)+1))for i in range(n+1)];"*d)
print(W[n])

Pruébalo en línea!

Termina el último caso de prueba en 0.078 s. La complejidad ingenua es O ( d n ² ).

Mathematica, 8 bytes, no competitiva

SquaresR

Jalea , 9 bytes

Nr⁸²ṗS€ċ⁸

Pruébalo en línea!

Toma ny den este orden.

MATL , 13 bytes

y_t_&:Z^U!s=s

Las entradas son n, entonces d. Algunos de los casos de prueba se quedan sin memoria.

Pruébalo en línea!

Explicación

Considere insumos 17, 3.

y     % Implicit inputs. Duplicate from below
      % STACK: 17, 3, 17
_     % Negate
      % STACK: 17, 3, -17
t_    % Duplicate. Negate
      % STACK: 17, 3, -17, 17
&:    % Two-input range
      % STACK: 17, 3, [-17 -16 ... 17]
Z^    % Cartesian power. Gives a matrix where each Cartesian tuple is a row
      % STACK: 17, [-17 -17 -17; -17 -17 -16; ...; 17 17 17]
U     % Square, element-wise
      % STACK: 17, [289 289 289; 289 289 256; ...; 289 289 289]
!s    % Transpose. Sum of each column
      % STACK: 17, [867 834 ... 867]
=     % Equals?, element-wise
      % STACK: 17, [0 0 ... 0] (there are 48 entries equal to 1 in between)
s     % Sum. Implicit display
      % STACK: 48

Haskell , 43 bytes

0#0=1
d#n=sum[(d-1)#(n-k*k)|d>0,k<-[-n..n]]

Solo tu recursión básica. Define una función de infijo binario #. Pruébalo en línea!

Explicación

0#0=1            -- If n == d == 0, give 1.
d#n=             -- Otherwise,
 sum[            -- give the sum of
  (d-1)#(n-k*k)  -- these numbers
  |d>0,          -- where d is positive
   k<-[-n..n]]   -- and k is between -n and n.

Si d == 0y n /= 0, estamos en el segundo caso, y la condición d>0hace que la lista esté vacía. La suma de la lista vacía es 0, que es la salida correcta en este caso.

Pari / GP , 31 bytes

d->n->sum(i=-n,n,x^i^2)^d\x^n%x

Pruébalo en línea!

05AB1E , 10 bytes

Ð(Ÿ²ã€nOQO

Toma los argumentos como n, luego d. Tiene problemas para resolver los casos de prueba más grandes.

Pruébalo en línea!

Explicación

Ð(Ÿ²ã€nOQO   Arguments n, d
Ð            Triplicate n on stack
 (           Negate n
  Ÿ          Range: [-n ... n]
   ²ã        Caertesian product of length d
     €n      Square each number
       OQ    Sum of pair equals n
         O   Total sum (number of ones)

Jalea , 23 bytes

‘ṬUµJ²fJ[0]ẋ;€ḤSḣL+µ⁹¡Ṫ

Pruébalo en línea!

Puerto de mi solución Python . Termina el último caso de prueba en 2.977 s.

Mathematica, 38 bytes

Count[Tr/@Tuples[Range[-#,#]^2,#2],#]&

Pura función de tomar las entradas en el orden n, d. Range[-#,#]^2da el conjunto de todos los cuadrados posiblemente relevantes, con cuadrados positivos listados dos veces para hacer el conteo correcto; Tuples[...,#2]produce las dtuplas de tales cuadrados; Tr/@suma cada dtupla; y Count[...,#]cuenta cuántos de los resultados son iguales n.

Los primeros casos de prueba terminan rápidamente, pero calculo que esto tomaría aproximadamente medio año para ejecutarse en el caso de prueba 1000,4. Reemplazar Range[-#,#]por el (más largo pero) más sensible Range[-Floor@Sqrt@#,Floor@Sqrt@#]acelera ese cálculo a unos 13 segundos.

Mathematica, 53 51 bytes

SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&

Pitón 2, 138

Solución muy ineficiente con mi querido eval. Por qué no?
Pruébalo en línea

lambda n,d:d and 4*eval(eval("('len({('+'i%s,'*d+'0)'+'for i%s in range(n)'*d+'if '+'i%s**2+'*d+'0==n})')%"+`tuple(range(d)*3)`),locals())

Genera y evalúa código como este:

len({(i0,i1,0)for i0 in range(n)for i1 in range(n)if i0**2+i1**2+0==n})

Entonces, para algunos d grandes , durará mucho y consumirá mucha memoria, teniendo una complejidad de O (n ^ d)

k , 23 bytes

{+/y=+/{x*x}y-!x#1+2*y}

Pruébalo en línea! Es un simple forzador bruto.

Pyth - 16 bytes

lfqQsm*ddT^}_QQE

Intentalo

Es horriblemente ineficiente