Zadanie
Biorąc pod uwagę dwie liczby całkowite d
i n
, znajdź liczbę sposobów wyrażenia n
jako sumę d
kwadratów. Oznacza to, n == r_1 ^2 + r_2 ^2 + ... + r_d ^2
że r_m
jest to liczba całkowita dla wszystkich liczb całkowitych 1 ≤ m ≤ d
. Zauważ, że zamiana dwóch różnych wartości (np. r_1
I r_2
) jest uważana za inną niż oryginalne rozwiązanie.
Na przykład liczbę 45 można zapisać jako sumę 2 kwadratów 8 różnych sposobów:
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
Zasady
- Wbudowane rozwiązania są dozwolone, ale niekonkurujące (ahem, Mathematica )
- Standardowe luki są również zabronione.
- Wejścia mogą być odwrócone.
Przykład 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
To jest golf golfowy , więc wygrane są przy użyciu najmniejszej ilości bajtów!
code-golf
number
number-theory
combinatorics
JungHwan Min
źródło
źródło
1, 0
testu, istnieje1
sposób, aby wyrazić0
jako sumę1
kwadratu:0 == 0^2
.Odpowiedzi:
Python 3 , 125 bajtów
Wypróbuj online!
Kończy ostatnią próbę za 0,078 s. Złożoność naiwna to O ( d n 2 ).
źródło
Mathematica, 8 bajtów, niekonkurujące
źródło
Galaretka , 9 bajtów
Wypróbuj online!
Trwa
n
id
w tej kolejności.źródło
MATL , 13 bajtów
Dane wejściowe są
n
zatemd
. W niektórych przypadkach testowych zabrakło pamięci.Wypróbuj online!
Wyjaśnienie
Rozważmy wejść
17
,3
.źródło
Haskell , 43 bajty
Tylko twoja podstawowa rekurencja. Definiuje funkcję binarnej poprawki
#
. Wypróbuj online!Wyjaśnienie
Jeśli
d == 0
in /= 0
, jesteśmy w drugim przypadku, a warunekd>0
powoduje, że lista jest pusta. Suma pustej listy wynosi 0, co w tym przypadku jest poprawnym wynikiem.źródło
Pari / GP , 31 bajtów
Wypróbuj online!
źródło
05AB1E , 10 bajtów
Przyjmuje argumenty jako n, a następnie d. Ma problemy z rozwiązywaniem większych przypadków testowych.
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka , 23 bajty
Wypróbuj online!
Port mojego rozwiązania Python . Kończy ostatnią próbę w ciągu 2,977 s.
źródło
Mathematica, 38 bajtów
Czysta funkcja biorąc wejść w kolejności
n
,d
.Range[-#,#]^2
podaje zestaw wszystkich możliwych kwadratów, z dodatnimi kwadratami wymienionymi dwukrotnie, aby liczba była poprawna;Tuples[...,#2]
produkujed
-tuple takich kwadratów;Tr/@
sumuje każdyd
-tuple; iCount[...,#]
liczy, ile wyników jest równychn
.Pierwsze kilka przypadków testowych kończy się szybko, ale szacuję, że uruchomienie tego przypadku zajęłoby około pół roku
1000,4
. ZastąpienieRange[-#,#]
(dłuższym, ale) bardziej sensownymRange[-Floor@Sqrt@#,Floor@Sqrt@#]
przyspiesza obliczenia do około 13 sekund.źródło
Mathematica,
5351 bajtówźródło
Python 2, 138
Bardzo nieefektywne rozwiązanie z moim ukochanym eval. Dlaczego nie?
Wypróbuj online
Wygenerował i ocenia kod w następujący sposób:
Więc dla niektórych dużych d będzie działać bardzo długo i zużyje dużo pamięci, mając złożoność O (n ^ d)
źródło
k , 23 bajty
Wypróbuj online! To prosty brutalny forcer.
źródło
Pyth - 16 bajtów
Spróbuj
To jest okropnie nieefektywne
źródło