Tâche

Étant donné deux nombres entiers det n, trouvez le nombre de façons d'exprimer nune somme de dcarrés. C'est-à- n == r_1 ^2 + r_2 ^2 + ... + r_d ^2dire que tel r_mest un entier pour tous les entiers 1 ≤ m ≤ d. Notez que l'échange de deux valeurs différentes (par exemple r_1et r_2) est considéré comme différent de la solution d'origine.

Par exemple, le nombre 45 peut être écrit comme une somme de 2 carrés de 8 manières différentes:

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

Règles

• Les solutions intégrées sont autorisées mais non concurrentes (ahem, Mathematica )
• Les failles standard sont également interdites.
• Les entrées peuvent être inversées.

Exemple d'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

C'est du code-golf , donc les soumissions utilisant le moins d'octets gagnent!

Python 3 , 125 octets

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])

Essayez-le en ligne!

Termine le dernier boîtier de test en 0,078 s. La complexité naïve est O ( d n ² ).

Mathematica, 8 octets, sans compétition

SquaresR

Gelée , 9 octets

Nr⁸²ṗS€ċ⁸

Essayez-le en ligne!

Prend net ddans cet ordre.

MATL , 13 octets

y_t_&:Z^U!s=s

Les entrées sont ndonc d. Certains cas de test manquent de mémoire.

Essayez-le en ligne!

Explication

Tenez compte des entrées 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 octets

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

Juste votre récursion de base. Définit une fonction d'infixe binaire #. Essayez-le en ligne!

Explication

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 == 0et n /= 0, nous sommes dans le deuxième cas, et la condition d>0fait que la liste est vide. La somme de la liste vide est 0, ce qui est la sortie correcte dans ce cas.

Pari / GP , 31 octets

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

Essayez-le en ligne!

05AB1E , 10 octets

Ð(Ÿ²ã€nOQO

Prend les arguments comme n, puis d. A des problèmes pour résoudre les plus gros cas de test.

Essayez-le en ligne!

Explication

Ð(Ÿ²ã€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)

Gelée , 23 octets

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

Essayez-le en ligne!

Port de ma solution Python . Termine le dernier testcase en 2.977 s.

Mathematica, 38 octets

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

Pure fonction de prendre les entrées dans l'ordre n, d. Range[-#,#]^2donne l'ensemble de tous les carrés éventuellement pertinents, avec des carrés positifs énumérés deux fois pour rendre le décompte correct; Tuples[...,#2]produit les d-tuples de ces carrés; Tr/@somme chaque d-tuple; et Count[...,#]compte combien de résultats sont égaux n.

Les premiers cas de test se terminent rapidement, mais j'estime qu'il faudrait environ six mois pour exécuter le cas de test 1000,4. Le remplacement Range[-#,#]par le (plus long mais) plus sensible Range[-Floor@Sqrt@#,Floor@Sqrt@#]accélère ce calcul à environ 13 secondes.

Mathematica, 53 51 octets

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

Python 2, 138

Solution très inefficace avec mon bien-aimé eval. Pourquoi pas?
Essayez-le en ligne

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())

Il a généré et évalue du code comme ceci:

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

Donc, pour certains gros d, il fonctionnera très longtemps et consommera beaucoup de mémoire, avec une complexité de O (n ^ d)

k , 23 octets

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

Essayez-le en ligne! C'est un simple forceur brutal.

Pyth - 16 octets

lfqQsm*ddT^}_QQE

Essayez-le

C'est horriblement inefficace