Aufgabe

Wenn zwei ganze Zahlen dund gegeben sind n, finden Sie die Anzahl der Ausdrücke nals Summe der dQuadrate. Das heißt, n == r_1 ^2 + r_2 ^2 + ... + r_d ^2dass dies r_meine ganze Zahl für alle ganzen Zahlen ist 1 ≤ m ≤ d. Beachten Sie, dass das Vertauschen von zwei verschiedenen Werten (z. B. r_1und r_2) als von der ursprünglichen Lösung abweichend angesehen wird.

Zum Beispiel kann die Zahl 45 als Summe von 2 Quadraten auf 8 verschiedene Arten geschrieben werden:

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

Regeln

• Eingebaute Lösungen sind erlaubt, aber nicht konkurrierend (ahem, Mathematica )
• Standardlücken sind ebenfalls verboten.
• Die Eingaben können vertauscht werden.

Beispiel I / O

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

Das ist Code-Golf , also gewinnen Einsendungen mit den wenigsten Bytes!

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

Probieren Sie es online!

Beendet den letzten Testfall in 0.078 s. Naive Komplexität ist O ( d n ² ).

Mathematica, 8 Bytes, nicht konkurrierend

SquaresR

Gelee , 9 Bytes

Nr⁸²ṗS€ċ⁸

Probieren Sie es online!

Nimmt nund din dieser Reihenfolge.

MATL , 13 Bytes

y_t_&:Z^U!s=s

Eingänge sind n dann d. Einige der Testfälle haben nicht genügend Arbeitsspeicher.

Probieren Sie es online!

Erläuterung

Betrachten Sie Eingänge 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]]

Nur Ihre Grundrekursion. Definiert eine binäre Infixfunktion #.Probieren Sie es online!

Erläuterung

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.

Wenn d == 0und n /= 0, sind wir im zweiten Fall und die Bedingung d>0bewirkt , dass die Liste leer ist. Die Summe der leeren Liste ist 0, was in diesem Fall die richtige Ausgabe ist.

Pari / GP , 31 Bytes

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

Probieren Sie es online!

05AB1E , 10 Bytes

Ð(Ÿ²ã€nOQO

Nimmt die Argumente als n, dann d. Hat Probleme die größeren Testfälle zu lösen.

Probieren Sie es online!

Erläuterung

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

Jelly , 23 Bytes

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

Probieren Sie es online!

Port meiner Python-Lösung . Beendet den letzten Testfall in 2.977 s.

Mathematica, 38 Bytes

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

Reine Funktion der Eingänge in der Reihenfolge nehmen n, d. Range[-#,#]^2gibt die Menge aller möglicherweise relevanten Quadrate an, wobei positive Quadrate zweimal aufgeführt sind, um die Zählung korrekt zu machen; Tuples[...,#2]erzeugt die dTupel solcher Quadrate; Tr/@summiert jedes dTupel; und Count[...,#]zählt, wie viele der Ergebnisse gleich sind n.

Die ersten paar Testfälle enden schnell, aber ich schätze, es würde ungefähr ein halbes Jahr dauern, bis der Testfall ausgeführt wird 1000,4. Das Ersetzen Range[-#,#]durch das (längere, aber) Vernünftigere Range[-Floor@Sqrt@#,Floor@Sqrt@#]beschleunigt diese Berechnung auf ungefähr 13 Sekunden.

Mathematica, 53 51 Bytes

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

Python 2, 138

Sehr ineffiziente Lösung mit meinem geliebten eval. Warum nicht?
Probieren Sie es online aus

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

Es generiert und wertet Code wie folgt aus:

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

Also für einige große d wird es sehr lange dauern und verbrauchen viel Speicher, mit der Komplexität von O (n ^ d)

k , 23 Bytes

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

Probieren Sie es online! Es ist ein einfacher Brute Forcer.

Pyth - 16 Bytes

lfqQsm*ddT^}_QQE

Versuch es

Es ist schrecklich ineffizient