Biorąc pod uwagę dwa dane wejściowe, q nokreśl, czy qjest kwadratową pozostałością n.

To znaczy, czy jest xgdzie x**2 == q (mod n)lub jest qkwadratowy mod n?

Wkład

Dwie liczby całkowite qoraz n, gdzie qi nsą dowolnymi liczbami całkowitymi 0 <= q < n.

Wydajność

Prawda czy falsey.

Opcjonalnie wydrukuj dowolny (lub wszystkie), xktóry jestx**2 == q (mod n)

Przykłady

>>> quadratic_residue(1, 5)
True
>>> quadratic_residue(3, 8)
False
>>> quadratic_residue(15, 22)
True

Zasady

Twój kod musi być programem lub funkcją. Wejścia mogą być w dowolnej kolejności. To jest kod golfowy, więc wygrywa najkrótszy kod w bajtach.

Jeśli coś jest niejasne lub w inny sposób wymaga naprawy, daj mi znać.

Bonusy

• 2-bajtowy bonus, jeśli twoja funkcja przyjmuje qdowolną liczbę całkowitą.

Katalog

var QUESTION_ID=65329;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Pyth, 9 bajtów

}Em%*ddQQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

}Em%*ddQQ   implicit: Q = first input number
  m     Q   map all numbers d of [0, 1, ..., Q-1] to:
    *dd       d*d
   %   Q      mod Q
            this gives the list of all quadratic residues
 E          read another input number
}           check, if it appears in the list of quadratic residues

Mathematica, 25 bajtów

AtomQ@PowerMod[#,1/2,#2]&

Mathematica, będąc Mathematica, ma oczywiście wbudowane narzędzie do obliczania modulo-tych pierwiastków za pośrednictwem PowerMod. Jeśli istnieje rozwiązanie, zwracane jest najmniejsze możliwe rozwiązanie, w przeciwnym razie oryginalne wyrażenie (plus komunikat).

Aby uzyskać rzeczywiste dane wyjściowe typu prawda / fałsz, przekazujemy wynik do AtomQ, który sprawdza, czy wyrażenie można rozbić. Liczby całkowite są atomowe, powracają True, podczas gdy nie-atomowe PowerMod[q,1/2,n]zwracaFalse

Dzięki @ MartinBüttner za wskazówki dotyczące golfa i polowanie na funkcje ze mną.

Par , 11 9 bajtów

✶X[²x%)↔,

Każda postać używa tylko jednego bajtu; patrz tutaj .

Wyjaśnienie

✶              ## Read two numbers
X              ## Assign second to x
[              ## Map
 ²             ## Square
 x%            ## Mod x
)              ## 
↔              ## Swap
,              ## Count

Usunięto dwa bajty dzięki Jakube.

LabVIEW, 16 15 Równoważne bajty

Policzone według mojego meta postu .

Haskell, 31 bajtów

Zaoszczędzono 3 bajty dzięki Martinowi Büttnerowi.

q#n=elem q[mod(x^2)n|x<-[1..n]]

Matlab, 29

Ta funkcja kwadratuje wszystkie liczby od 0 do n i sprawdza, czy kwadrat minus q jest zerowy mod n.

@(q,n)any(~mod((0:n).^2-q,n))

Prolog (SWI), 34 bajty

Kod:

Q*N:-between(0,N,X),X*X mod N=:=Q.

Objaśnienie:
Kontrole jeśli kwadratowe między 0 a N li Q gdy podzielone przez N .

Przykład:

3*8.
false

15*22.
true

Wypróbuj online tutaj

CJam, 11 bajtów

{_,2f#\f%&}

Ten nienazwany blok oczekuje q nna stosie i pozostawia [q]na stosie wartość prawdziwą lub ""fałszywą.

Sprawdź to tutaj.

Podziękowania dla Sp3000, który również wymyślił to rozwiązanie, ale „nie można go było niepokoić”.

Wyjaśnienie

_,  e# Duplicate n and turn into range [0 1 ... n-1]
2f# e# Square each element in the range.
\f% e# Take each element in the range modulo n.
&   e# Set intersection with q to check if any square yields q (mod n).

J, 9 bajtów

e.]|i.^2:

Stosowanie:

   1 (e.]|i.^2:) 5
1
   3 (e.]|i.^2:) 8
0
   15 (e.]|i.^2:) 22
1

Wyjaśnienie:

e.]|i.^2:
    i.    [0..N-1]
      ^   to the power of
       2: 2 (constant 2 function)
  ]|      mod N       
e.        contains Q? (0/1 result)

Kilka ciekawostek mechaniki J:

Funkcje są grupowane po 3 iteracyjnie od prawej, a jeśli jest jedna, tak jak w naszym przypadku ( e. (] | (i. ^ 2:))), część zgrupowana jest wywoływana za pomocą prawego argumentu ( N), a funkcja pominięta ( e.„zawiera”) wywoływana z oryginalną lewą argument ( Q) i wynik zgrupowanej części.

( e.]|i.*i.a e.]|2^~i.także rozwiązuje problem o tej samej długości).

Wypróbuj online tutaj.

Mathematica, 27 bajtów

PowerModList[#,1/2,#2]!={}&

Stosowanie:

In[1]:= PowerModList[#,1/2,#2]!={}&[1,5]

Out[1]= True

JavaScript ES6, 42 bajty

(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)

Zapisano kredyty dla @apsilers za poważne bajty!

Poważnie , 20 bajtów

,;R@,;╗@%╝`ª╜@%╛=`MΣ

Pobiera dane wejściowe w dwóch wierszach: qnastępnie n. Wyprowadza 0jeśli qnie jest reszta kwadratowa z n, jeszcze dodatnia liczba reprezentująca ile xw [1, q](włącznie) spełniają x^2 = q (mod n).

Wypróbuj online (permalinki mają więcej problemów, ale w międzyczasie możesz skopiować i wkleić kod na pustej stronie )

Wyjaśnienie:

,;R      get q input, duplicate, push range(1, q+1)
@,;╗     move the list to the back of the stack, get n input, dupe, save in reg 0
@%╝      calculate q mod n and save to reg 1
`ª╜@%╛=` push this function:
  ª╜@%     square top of stack, push reg 0 value (n), swap, and mod
  ╛=       push reg 1 value (q mod n), compare equality (1 if equal else 0)
MΣ       map the function across the range, add results

Python 3, 41 40 bajtów

Pobiera qi nokreśla, czy qjest na liście kwadratów od 0kwadratu do n-1kwadratu.

lambda q,n:q in[i*i%n for i in range(n)]

Rubin, 33 31 bajtów

Zaoszczędzono dwa bajty dzięki Vasu Adari.

->q,n{(1..n).any?{|e|e*e%n==q}}

Jak zwykle Ruby nie pokona żadnego z golfowych języków, ale dobrze się tu prezentuje.

Julia, 30 bajtów

f(q,n)=q∈[i^2%n for i=0:n-1]

Jest to funkcja, fktóra akceptuje dwie liczby całkowite i zwraca wartość logiczną.

Nie golfowany:

function f(q::Integer, n::Integer)
    # Generate an array of quadratic residues
    x = [i^2 % n for i = 0:n-1]

    # Determine whether q is one of these values
    return q ∈ x
end

JavaScript (ES6), 43 bajty

(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

Wyjaśnienie

(q,n)=>
  eval(`              // eval allows us to use a for loop without {} or return
    for(x=n,r=0;x--;) // iterate over all possible values of x
      r+=x*x%n==q     // r = the number of matching x values
  `)                  // implicit: return r

Test

q = <input type="number" id="Q" /><br />
n = <input type="number" id="N" /><br />
<button onclick="result.innerHTML=(

(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

)(+Q.value,+N.value)">Go</button><pre id="result"></pre>

𝔼𝕊𝕄𝕚𝕟, 13 znaków / 25 bajtów

⟦Ѧí]ĉ⇀_²%í≔î)

Try it here (Firefox only).

Japt, 10 bajtów

Vo d_²%V¥U

Mój pierwszy oficjalny golf Japt w historii! Dzięki @ETHProductions za uratowanie bajtu!

Niegolfowane / Wyjaśnienie

Vo d_  ²  %V¥ U
Vo dZ{Zp2 %V==U}  // implicit: U,V = inputs
Vo                // Create a range from 0 to n-1
   dZ{         }  // Check if any element Z in the range satisfies the condition:
       Zp2        // Is Z squared...
           %V     // modulo n...
             ==U  // equal to q?
                  // implicit output

Wypróbuj online!

C # 6 (.Net Framework 4.6) w LinqPad, 60 bajtów

bool b(int q,int n)=>Enumerable.Range(1,n).Any(y=>y*y%n==q);

Droga Mleczna 1.0.2 , 41 bajtów

:>&{~1-:2h<:>n>;:>;<<b?{_a0_^}~;?{_0_1}}!

Oczekuje qi nbędzie wyłącznie na stosie. Wyprowadza odpowiednio a 1lub 0prawdę i fałsz.

Pari / GP , 25 bajtów

(q,n)->issquare(Mod(q,n))

Wypróbuj online!

JavaScript (Node.js) , 33 bajty

q=>n=>f=(t=n)=>t&&f(t-1)|t*t%n==q

Wypróbuj online!

Dlaczego nikt tego nie robi