Dadas duas entradas, q ndetermine se qé um resíduo quadrático de n.

Ou seja, existe um xonde x**2 == q (mod n)ou qum mod quadrado n?

Entrada

Dois números inteiros qe n, onde qe nsão quaisquer números inteiros 0 <= q < n.

Saída

Uma verdade ou um falsey.

Opcionalmente, imprima qualquer um (ou todos) xque estejax**2 == q (mod n)

Exemplos

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

Regras

Seu código deve ser um programa ou uma função. As entradas podem estar em qualquer ordem. Este é o código golf, pelo que o código mais curto em bytes vence.

Se algo não estiver claro ou precisar de conserto, entre em contato.

Bónus

• Bônus de 2 bytes se sua função aceitar qcomo qualquer número inteiro arbitrário.

Catálogo

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>

Pitão, 9 bytes

}Em%*ddQQ

Experimente on-line: Demonstration or Test Suite

Explicação:

}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 bytes

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

O Mathematica, sendo o Mathematica, naturalmente possui um mecanismo embutido para o cálculo de raízes modulares, via PowerMod. Se existir uma solução, a menor solução possível será retornada, caso contrário, a expressão original (mais uma mensagem).

Para obter uma saída real de verdade / falsidade, passamos o resultado para AtomQ, que verifica se uma expressão pode ser dividida. Inteiros são atômicos, retornando True, enquanto os PowerMod[q,1/2,n]retornos não atômicosFalse

Agradeço a @ MartinBüttner por dicas de golfe e caça de funções comigo.

Par , 11 9 bytes

✶X[²x%)↔,

Cada caractere usa apenas um byte; veja aqui .

Explicação

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

Removidos dois bytes graças a Jakube.

LabVIEW, 16 15 bytes equivalentes

Contado de acordo com o meu meta post .

Haskell, 31 bytes

Economizou 3 bytes graças a Martin Büttner.

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

Matlab, 29

Esta função esquadrinha todos os números de 0 a n e verifica se um quadrado menos q é zero mod n.

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

Prolog (SWI), 34 bytes

Código:

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

Explicação:
Verifica se qualquer quadrado entre 0 e N folhas Q quando dividido por N .

Exemplo:

3*8.
false

15*22.
true

Experimente online aqui

CJam, 11 bytes

{_,2f#\f%&}

Esse bloco sem nome espera q nna pilha e deixa [q]na pilha como um valor ""verdadeiro ou falso.

Teste aqui.

Créditos ao Sp3000 que também criaram esta solução, mas "não se incomodaram em postar".

Explicação

_,  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 bytes

e.]|i.^2:

Uso:

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

Explicação:

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

Algumas curiosidades da mecânica J:

As funções são agrupadas por 3 iterativamente da direita e, se houver uma esquerda, como no nosso caso ( e. (] | (i. ^ 2:))), a parte agrupada é chamada com o argumento direito ( N) e a função deixada de fora ( e., "contém") chamada com a esquerda original argument ( Q) e o resultado da parte agrupada.

( e.]|i.*i.e e.]|2^~i.também resolve o problema com o mesmo comprimento.)

Experimente online aqui.

Mathematica, 27 bytes

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

Uso:

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

Out[1]= True

Javascript ES6, 42 bytes

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

Créditos para @apsilers por bytes sérios salvos!

Sério , 20 bytes

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

Recebe entrada em duas linhas:, qentão n. Emite um 0if qse não for um resíduo quadrático de n, senão um número positivo representando quantos xem [1, q](inclusive) satisfazem x^2 = q (mod n).

Experimente on-line (os links permanentes estão com mais problemas, mas você pode copiar e colar o código em uma página em branco )

Explicação:

,;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 bytes

Toma qe ne determina se qestá em uma lista de quadrados de 0quadrado para n-1quadrado.

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

Ruby, 33 31 bytes

Economizou dois bytes graças a Vasu Adari.

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

Como de costume, Ruby não vai vencer nenhuma das línguas do golfe, mas faz uma boa exibição aqui.

Julia, 30 bytes

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

Esta é uma função fque aceita dois números inteiros e retorna um booleano.

Ungolfed:

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 bytes

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

Explicação

(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

Teste

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 caracteres / 25 bytes

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

Try it here (Firefox only).

Japonês, 10 bytes

Vo d_²%V¥U

Meu primeiro golfe oficial de Japt! Agradecemos a @ETHProductions por salvar um byte!

Ungolfed / Explicação

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

Experimente online!

C # 6 (.Net Framework 4.6) no LinqPad, 60 bytes

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

Via Láctea 1.0.2 , 41 bytes

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

Isso espera qe ndeve estar apenas na pilha. Ele gera a 1ou 0para os valores verdade e falso, respectivamente.

Pari / GP , 25 bytes

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

Experimente online!

JavaScript (Node.js) , 33 bytes

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

Experimente online!

Por que ninguém faz isso