¿Es qa un residuo cuadrático de n?

22

Dadas dos entradas q ndeterminar si qes un residuo cuadrático de n.

Es decir, ¿hay un xdónde x**2 == q (mod n)o hay qun mod cuadrado n?

Entrada

Dos enteros qy n, donde qy nson enteros 0 <= q < n.

Salida

Una verdad o una falsey.

Opcionalmente, imprima cualquier (o todo) xque 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 qcomo 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>

Sherlock9
fuente
55
Algunas respuestas existentes están asumiendo eso 0 <= q < n. Probablemente debería aclarar si esta es una suposición aceptable o no.
Peter Taylor
1
Me hubiera gustado qy nque cualquier par de números enteros, pero lo que no se rompen respuestas existentes,0 <= q < n
Sherlock9
2
En este caso, habría considerado razonable "romper" las respuestas existentes con el argumento de que no estaban siguiendo la especificación existente y solo estaba aclarando que significaba lo que decía en lugar de cambiarla, pero ahora es demasiado tarde.
Peter Taylor
Podría dar una pequeña bonificación por las soluciones que acepten arbitrariasq
Bakuriu

Respuestas:

6

Pyth, 9 bytes

}Em%*ddQQ

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

}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
Jakube
fuente
Traté de poner 7 9 como entradas, y decía "Falso", a pesar de que 7 es equivalente a 5 ^ 2 mod 9.
Nick Matteo
@kundor Leí los enteros en el orden inverso. Primero ny que q. Intenta 9\n7como entrada.
Jakube
8

Mathematica, 25 bytes

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

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, regresan True, mientras que los no atómicos PowerMod[q,1/2,n]retornanFalse

Gracias a @ MartinBüttner por los consejos de golf y la búsqueda de funciones conmigo.

Sp3000
fuente
Estúpido ordenamiento de argumentos
CalculatorFeline
¡¿Qué?! ¡Nunca supe que PowerModpodría tomar una discusión fraccional!
Greg Martin
8

Par , 11 9 bytes

✶X[²x%)↔,

Cada personaje usa solo un byte; ver aquí .

Explicación

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

Se eliminaron dos bytes gracias a Jakube.

Ypnypn
fuente
5

Haskell, 31 bytes

Guardado 3 bytes gracias a Martin Büttner.

q#n=elem q[mod(x^2)n|x<-[1..n]]
alephalpha
fuente
1
También 31 bytes: 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.
nimi
5

Matlab, 29

Esta función cuadra todos los números del 0 al ny comprueba si un cuadrado menos q es cero mod n.

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

Prólogo (SWI), 34 bytes

Código:

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

Explicación:
Comprueba si cualquier cuadrado entre 0 y N hojas Q cuando se divide por N .

Ejemplo:

3*8.
false

15*22.
true

Pruébalo en línea aquí

Emigna
fuente
4

CJam, 11 bytes

{_,2f#\f%&}

Este bloque sin nombre se espera q nen 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

_,  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).
Martin Ender
fuente
4

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

Explicación:

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

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.y e.]|2^~i.también resuelve el problema con la misma longitud).

Pruébelo en línea aquí.

randomra
fuente
3

Mathematica, 27 bytes

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

Uso:

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

Out[1]= True
alephalpha
fuente
3

Javascript ES6, 42 bytes

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

¡Créditos a @apsilers por bytes serios guardados!

Mama Fun Roll
fuente
¿Cuál es la ...Arraysintaxis? Aún no lo entiendo.
Tomáš Zato - Restablece a Mónica el
Espero que esta edición sea mejor para ti.
Mama Fun Roll
[...Array(5)]produce una matriz de undefined, igual que Array(5)solo. Estoy totalmente confundido, porque eliminar la sintaxis extraña y usarlo simplemente Array(5)rompe el código. ¿Hay alguna documentación para esto? captura de pantalla de mi consola
Tomáš Zato - Restablecer Monica
1
@ TomášZato Array(5)es una matriz sin propiedades propias excepto length. La distribución de matriz completa [...x]las propiedades numéricas faltantes hasta length. La mapfunción solo puede operar en propiedades existentes, que Array(5)solo no tiene. Por ejemplo, intente Array(5).hasOwnProperty(0)(falso) versus [...Array(5)].hasOwnProperty(0)(verdadero).
apsillers
1
Además, el uso somees más corto y (creo) equivalente:(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)
apsillers
2

En serio , 20 bytes

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

Toma entrada en dos líneas:, qentonces n. Emite un 0if si qno es un residuo cuadrático de n, sino un número positivo que representa cuántos xen [1, q](inclusive) satisfacen x^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:

,;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
Mego
fuente
2

Python 3, 41 40 bytes

Toma qy ny determina si qestá en una lista de cuadrados de 0cuadrado a n-1cuadrado.

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

Ruby, 33 31 bytes

Ahorré dos bytes gracias a Vasu Adari.

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

Como de costumbre, Ruby no va a vencer a ninguno de los idiomas de golf, pero hace una buena presentación aquí.

Restablecer a Monica iamnotmaynard
fuente
Puedes perder los frenos y hacerlo ->q,n{}.
Vasu Adari
@VasuAdari Cool, no lo sabía. Gracias.
Reinstale a Monica iamnotmaynard el
1

Julia, 30 bytes

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

Esta es una función fque acepta dos enteros y devuelve un valor booleano.

Sin 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
Alex A.
fuente
1

JavaScript (ES6), 43 bytes

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

Explicación

(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

Prueba

usuario81655
fuente
Esta es una versión muy interesante de la condición de verdad / falsa @ user81655. ¡Excelente trabajo!
Sherlock9
1

𝔼𝕊𝕄𝕚𝕟, 13 caracteres / 25 bytes

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

Try it here (Firefox only).

Mama Fun Roll
fuente
1
Probé tu código con 15 22y decía false.
Sherlock9
@ Sherlock9 Fijo.
Mama Fun Roll
¿No hay una página de códigos personalizada? ¡Este no es un lenguaje de golf!
CalculatorFeline
Ahora sí, pero la página de códigos se hizo mucho después del desafío.
Mama Fun Roll
1

Japt, 10 bytes

Vo d_²%V¥U

¡Mi primer Japt Golf oficial! ¡Gracias a @ETHProductions por guardar un byte!

Ungolfed / Explicación

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

Pruébalo en línea!

Mama Fun Roll
fuente
1
¡Agradable! Sugerencia: 0oVes equivalente a Vo.
ETHproductions
No lo sabia. ¡Gracias!
Mama Fun Roll
0

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

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

Vía Láctea 1.0.2 , 41 bytes

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

Esto espera qy nestará únicamente en la pila. Da salida a 1o0 para los valores de verdad y falso, respectivamente.

Puertas de Zach
fuente