Étant donné deux entrées, q ndéterminez si qest un résidu quadratique de n.

Autrement dit, y a-t-il un xoù x**2 == q (mod n)ou qun mod carré n?

Contribution

Deux entiers qet n, où qet nsont des entiers 0 <= q < n.

Sortie

Un vrai ou un falsey.

En option, imprimer tout (ou tout) xqui estx**2 == q (mod n)

Exemples

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

Règles

Votre code doit être un programme ou une fonction. Les entrées peuvent être dans n'importe quel ordre. C'est le code golf, donc le code le plus court en octets l'emporte.

Si quelque chose n'est pas clair ou doit être réparé, faites-le moi savoir.

Bonus

• Bonus de 2 octets si votre fonction accepte qcomme n'importe quel entier arbitraire.

Catalogue

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 octets

}Em%*ddQQ

Essayez-le en ligne: démonstration ou suite de tests

Explication:

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

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

Mathematica, étant Mathematica, a naturellement une fonction intégrée pour calculer les racines modulatives, via PowerMod . Si une solution existe, la plus petite solution possible est renvoyée, sinon l'expression d'origine (plus un message).

Pour obtenir une sortie véridique / fausse réelle, nous transmettons le résultat à AtomQ, qui vérifie si une expression peut être décomposée. Les entiers sont atomiques, retournant True, tandis que les PowerMod[q,1/2,n]retours non atomiquesFalse

Merci à @ MartinBüttner pour les conseils de golf et la recherche de fonctions avec moi.

Par , 11 9 octets

✶X[²x%)↔,

Chaque caractère utilise un seul octet; voir ici .

Explication

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

Suppression de deux octets grâce à Jakube.

LabVIEW, 16 15 octets équivalents

Compté selon mon meta post .

Haskell, 31 octets

Enregistré 3 octets grâce à Martin Büttner.

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

Matlab, 29

Cette fonction met au carré tous les nombres de 0 à n et vérifie si un carré moins q est zéro mod n.

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

Prolog (SWI), 34 octets

Code:

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

Explication:
vérifie si un carré entre 0 et N laisse Q lorsqu'il est divisé par N .

Exemple:

3*8.
false

15*22.
true

Essayez-le en ligne ici

CJam, 11 octets

{_,2f#\f%&}

Ce bloc sans nom attend q nsur la pile et reste [q]sur la pile comme une valeur véridique ou"" comme valeur fausse.

Testez-le ici.

Remerciements à Sp3000 qui a également proposé cette solution mais "ne pouvait pas être dérangé par la publication".

Explication

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

e.]|i.^2:

Usage:

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

Explication:

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

Quelques anecdotes sur la mécanique J:

Les fonctions sont regroupées par 3 de manière itérative à partir de la droite et s'il y en a une à gauche, comme dans notre cas ( e. (] | (i. ^ 2:))), la partie groupée est appelée avec l'argument de droite ( N) et la fonction de gauche ( e., "contient") appelée avec la gauche d'origine argument ( Q) et le résultat de la partie groupée.

( e.]|i.*i.et e.]|2^~i.résout également le problème avec la même longueur.)

Essayez-le en ligne ici.

Mathematica, 27 octets

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

Usage:

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

Out[1]= True

Javascript ES6, 42 octets

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

Crédits à @apsilers pour les octets sérieux enregistrés!

Sérieusement , 20 octets

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

Prend la saisie sur deux lignes:, qpuis n. Produit un 0if qui qn'est pas un résidu quadratique de n, sinon un nombre positif représentant le nombre xen [1, q](inclus) satisfait x^2 = q (mod n).

Essayez-le en ligne (les permaliens ont plus de problèmes, mais vous pouvez copier et coller le code dans une page vierge en attendant)

Explication:

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

Prend qet ndétermine si se qtrouve dans une liste de carrés du 0carré au n-1carré.

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

Rubis, 33 31 octets

Enregistré deux octets grâce à Vasu Adari.

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

Comme d'habitude, Ruby ne battra aucune des langues de golf, mais cela fait une bonne performance ici.

Julia, 30 octets

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

Il s'agit d'une fonction fqui accepte deux entiers et renvoie un booléen.

Non golfé:

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 octets

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

Explication

(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

Tester

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 caractères / 25 octets

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

Try it here (Firefox only).

Japt, 10 octets

Vo d_²%V¥U

Mon tout premier golf Japt officiel! Merci à @ETHProductions d'avoir enregistré un octet!

Non golfé / Explication

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

Essayez-le en ligne!

C # 6 (.Net Framework 4.6) dans LinqPad, 60 octets

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

Voie lactée 1.0.2 , 41 octets

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

Cela attend qet nd'être uniquement sur la pile. Il génère respectivement un 1ou 0pour la vérité et les fausses valeurs.

Pari / GP , 25 octets

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

Essayez-le en ligne!

JavaScript (Node.js) , 33 octets

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

Essayez-le en ligne!

Pourquoi personne ne fait ça