Dadas dos entradas q n
determinar si q
es un residuo cuadrático de n
.
Es decir, ¿hay un x
dónde x**2 == q (mod n)
o hay q
un mod cuadrado n
?
Entrada
Dos enteros q
y n
, donde q
y n
son enteros 0 <= q < n
.
Salida
Una verdad o una falsey.
Opcionalmente, imprima cualquier (o todo) x
que seax**2 == q (mod n)
Ejemplos
>>> quadratic_residue(1, 5)
True
>>> quadratic_residue(3, 8)
False
>>> quadratic_residue(15, 22)
True
Reglas
Su código debe ser un programa o una función. Las entradas pueden estar en cualquier orden. Este es el código de golf, por lo que gana el código más corto en bytes.
Si algo no está claro o necesita ser reparado, hágamelo saber.
Bonos
- Bonificación de 2 bytes si su función acepta
q
como un entero arbitrario.
Catalogar
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>
code-golf
math
arithmetic
number-theory
Sherlock9
fuente
fuente
0 <= q < n
. Probablemente debería aclarar si esta es una suposición aceptable o no.q
yn
que cualquier par de números enteros, pero lo que no se rompen respuestas existentes,0 <= q < n
q
Respuestas:
Pyth, 9 bytes
Pruébelo en línea: Demostración o conjunto de pruebas
Explicación:
fuente
n
y queq
. Intenta9\n7
como entrada.Mathematica, 25 bytes
Mathematica, siendo Mathematica, naturalmente tiene una función incorporada para calcular las raíces del módulo n, a través de
PowerMod
. Si existe una solución, se devuelve la solución más pequeña posible; de lo contrario, la expresión original (más un mensaje).Para obtener una salida de verdad / falsedad real, pasamos el resultado a
AtomQ
, que verifica si una expresión puede descomponerse. Los enteros son atómicos, regresanTrue
, mientras que los no atómicosPowerMod[q,1/2,n]
retornanFalse
Gracias a @ MartinBüttner por los consejos de golf y la búsqueda de funciones conmigo.
fuente
PowerMod
podría tomar una discusión fraccional!Par ,
119 bytesCada personaje usa solo un byte; ver aquí .
Explicación
Se eliminaron dos bytes gracias a Jakube.
fuente
LabVIEW,
1615 bytes equivalentesContada según mi meta publicación .
fuente
Haskell, 31 bytes
Guardado 3 bytes gracias a Martin Büttner.
fuente
q#n=any(\x->mod(x*x)n==q)[0..n]
y para 30 bytes:q#n=[x|x<-[0..n],mod(x*x)n==q]
que devuelve la lista de x / lista vacía en lugar de Verdadero / Falso.Matlab, 29
Esta función cuadra todos los números del 0 al ny comprueba si un cuadrado menos q es cero mod n.
fuente
Prólogo (SWI), 34 bytes
Código:
Explicación:
Comprueba si cualquier cuadrado entre 0 y N hojas Q cuando se divide por N .
Ejemplo:
Pruébalo en línea aquí
fuente
CJam, 11 bytes
Este bloque sin nombre se espera
q n
en la pila y se deja[q]
en la pila como un valor verdadero o""
como un valor falso.Pruébalo aquí.
Créditos a Sp3000, a quien también se le ocurrió esta solución, pero "no podía molestarse en publicar".
Explicación
fuente
J, 9 bytes
Uso:
Explicación:
Algunas curiosidades de la mecánica J:
Las funciones se agrupan por 3 iterativamente desde la derecha y si queda una, como en nuestro caso (
e. (] | (i. ^ 2:))
), la parte agrupada se llama con el argumento derecho (N
) y la función de exclusión ((e.
"contiene") se llama con la izquierda original argumento (Q
) y el resultado de la parte agrupada.(
e.]|i.*i.
ye.]|2^~i.
también resuelve el problema con la misma longitud).Pruébelo en línea aquí.
fuente
Mathematica, 27 bytes
Uso:
fuente
Javascript ES6, 42 bytes
¡Créditos a @apsilers por bytes serios guardados!
fuente
...Array
sintaxis? Aún no lo entiendo.[...Array(5)]
produce una matriz deundefined
, igual queArray(5)
solo. Estoy totalmente confundido, porque eliminar la sintaxis extraña y usarlo simplementeArray(5)
rompe el código. ¿Hay alguna documentación para esto? captura de pantalla de mi consolaArray(5)
es una matriz sin propiedades propias exceptolength
. La distribución de matriz completa[...x]
las propiedades numéricas faltantes hastalength
. Lamap
función solo puede operar en propiedades existentes, queArray(5)
solo no tiene. Por ejemplo, intenteArray(5).hasOwnProperty(0)
(falso) versus[...Array(5)].hasOwnProperty(0)
(verdadero).some
es más corto y (creo) equivalente:(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)
En serio , 20 bytes
Toma entrada en dos líneas:,
q
entoncesn
. Emite un0
if siq
no es un residuo cuadrático den
, sino un número positivo que representa cuántosx
en[1, q]
(inclusive) satisfacenx^2 = q (mod n)
.Pruébelo en línea (los enlaces permanentes tienen más problemas, pero puede copiar y pegar el código en una página en blanco mientras tanto)
Explicación:
fuente
Python 3,
4140 bytesToma
q
yn
y determina siq
está en una lista de cuadrados de0
cuadrado an-1
cuadrado.fuente
Ruby,
3331 bytesAhorré dos bytes gracias a Vasu Adari.
Como de costumbre, Ruby no va a vencer a ninguno de los idiomas de golf, pero hace una buena presentación aquí.
fuente
->q,n{}
.Julia, 30 bytes
Esta es una función
f
que acepta dos enteros y devuelve un valor booleano.Sin golf:
fuente
JavaScript (ES6), 43 bytes
Explicación
Prueba
Mostrar fragmento de código
fuente
𝔼𝕊𝕄𝕚𝕟, 13 caracteres / 25 bytes
Try it here (Firefox only).
fuente
15 22
y decíafalse
.Japt, 10 bytes
¡Mi primer Japt Golf oficial! ¡Gracias a @ETHProductions por guardar un byte!
Ungolfed / Explicación
Pruébalo en línea!
fuente
0oV
es equivalente aVo
.C # 6 (.Net Framework 4.6) en LinqPad, 60 bytes
fuente
Vía Láctea 1.0.2 , 41 bytes
Esto espera
q
yn
estará únicamente en la pila. Da salida a1
o0
para los valores de verdad y falso, respectivamente.fuente
Pari / GP , 25 bytes
Pruébalo en línea!
fuente
JavaScript (Node.js) , 33 bytes
Pruébalo en línea!
¿Por qué nadie hace esto?
fuente