Calcular el módulo inverso

18

La tarea:

Salida de un valor para x, donde a mod x = bpara dos valores dadosa,b .

Suposición

  • a y b siempre serán enteros positivos
  • No siempre habrá una solución para x
  • Si existen varias soluciones, envíe al menos una de ellas.
  • Si no hay soluciones, no envíe nada o alguna indicación de que no existen soluciones.
  • Se permiten los elementos integrados (no tan divertidos como otros enfoques matemáticos)
  • Las salidas son siempre enteras

Ejemplos

A, B >> POSSIBLE OUTPUTS

5, 2 >> 3
9, 4 >> 5
8, 2 >> 3, 6
6, 6 >> 7, (ANY NUMBER > 6)
8, 7 >> NO SOLUTION
2, 4 >> NO SOLUTION
8, 5 >> NO SOLUTION
10,1 >> 3, 9

Este es el , por lo que gana los bytes más bajos.

Graviton
fuente
¿Puede error si no se encuentra una solución?
aplaude
@ConfusedMr_C Técnicamente eso no indica ninguna solución, entonces sí.
Graviton

Respuestas:

11

JavaScript , 28 27 26 24 23 bytes

a=>b=>(a-=b)?a>b&&a:b+1

Pruébalo en línea!

false indica que no hay solución

-1 gracias @Arnauld

eush77
fuente
Bien hecho y muy bien golfizado.
Shaggy
Entonces, para llamarlo, debe darle un nombre a la función externa, por ejemplo f=..., f(8)(3)¿ llamar ? ¿Eso parece un poco descarado? La forma normal de llamar a una función sería f(8,3), ¿qué alargaría la definición de su función?
Steve Bennett
3
@SteveBennett Cierto, la definición es curiosa , lo que significa que debe llamarse así (8)(3), pero existe un consenso sobre PPCG que está permitido . Sin embargo, no tienes que darle un nombre.
eush77
1
@SteveBennett Es divertido cómo crees que 26 vs -15 es todo menos un claro consenso. Buena suerte intentando disputar.
eush77
1
@SteveBennett, ¿cómo es 55 a 1 un consenso débil?
Cyoce
6

MATL , 6 bytes

tQ:\=f

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Considere las entradas 8, 2como un ejemplo.

t    % Implicit input. Duplicate                STACK: 8, 8
Q    % Add 1                                    STACK: 8, 9
:    % Range                                    STACK: 8, [1 2 3 4 5 6 7 8 9]
\    % Modulo                                   STACK: [0 0 2 0 3 2 1 0 8]
=    % Implicit input. Equality comparison      STACK: [0 0 1 0 0 1 0 0 0]
f    % Indices of nonzeros. Implicit display    STACK: [3 6]
Luis Mendo
fuente
3

Groovy, 48 bytes (usando incorporado):

{a,b->Eval.me(a+"g").modInverse(Eval.me(b+"g"))}

Eval.me(...+"g") - Fija "g" en la entrada, convirtiéndola en un BigInteger.

modInverse(...) - Realiza la operación de módulo inverso.


Java 8, 70 bytes

{a,b->return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(b));}
Urna de pulpo mágico
fuente
3

R , 33 28 bytes

pryr::f(match(b,a%%1:(a+1)))

Pruébalo en línea!

-4 bytes gracias a Jarko Dubbeldam.

-1 byte gracias a Giuseppe.

Devuelve NAsi no hay solución. TIO no tiene instalada la biblioteca pryr, por lo que se utiliza el código en ese enlace function(a,b).

Nitrodon
fuente
pryr::f(which(a%%1:(a+1)==b)) es 4 bytes más corto.
JAD
También puede soltar otro byte utilizando match(b,a%%1:(a+1)), que devuelve NAun valor faltante.
Giuseppe
1

Jalea , 11 10 bytes

³%_⁴
r‘ÇÐḟ

Un programa completo de tomar los dos números enteros positivos, ay b, y la impresión de una lista de las soluciones enteras entre min(a,b)+1y max(a,b)+1inclusivas.

Pruébalo en línea!

Jonathan Allan
fuente
1

Mathematica 36 Bytes

a_±b_:=Select[Range[9a],a~Mod~#==b&]

Entrada:

5 ± 2
9 ± 4
8 ± 2
6 ± 6
8 ± 7
2 ± 4
8 ± 5
10 ± 1

Salida:

{3}
{5}
{3, 6}
{7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, \
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, \
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54}
{}
{}
{}
{3, 9}
Kelly Lowder
fuente
Cuando se utilizan estos operadores ASCII extendidos en forma binaria, necesitan un espacio al frente cuando se definen, de lo contrario, el analizador arroja un error. Entonces tendría que ser así a_ ±b_. Pero de todos modos es más corto de usar en Caseslugar de Selectuna función sin nombre:Cases[Range[9#],x_/;#~Mod~x==#2]&
Martin Ender
1

Haskell , 33 bytes

Se bloquea con code.hs: out of memory (requested ??? bytes)si no hay solución (se agota el tiempo de espera en TIO antes de eso):

a!b=[x|x<-[b+1..],mod(a-b)x<1]!!0

Pruébalo en línea!

¡Gracias a Ørjan Johansen por detectar un error!

ბიმო
fuente
Esto da respuestas incorrectas para los casos de prueba donde se bdivide a.
Ørjan Johansen
1

C # (compilador Mono C #) , 57 56 26 bytes

La respuesta de Python al puerto de Rod . Gracias a WW por -1 byte.

ENORMES gracias a Kevin Cruijssen por -30 bytes.

a=>b=>a-b>b?a-b:a==b?a+1:0

Pruébalo en línea!

Epicness
fuente
1
Bienvenido al sitio! Parece que puedes eliminar el espacio después return.
Wheat Wizard
Bienvenido a PPCG! Para las respuestas no recursivas de C # siempre es mejor y más corto usar una función lambda ( i=>{/*code here*/}). Sin embargo, en este caso, dado que tiene 2 entradas, puede ser una función lambda curry para guardar un byte adicional (en a=>b=>{/*code here*/}lugar de (a,b)=>{/*code here*/}). Además, puede eliminar el paréntesis alrededor de sus verificaciones if. En total, sin cambiar ninguna de sus funciones, se convierte en a=>b=>a-b>b?a-b:a==b?a+1:0 26 bytes
Kevin Cruijssen
Además, si aún no lo ha visto, los consejos para jugar golf en <todos los idiomas> y los consejos para jugar golf en C # pueden ser interesantes de leer. ¡Disfruta tu estancia! :)
Kevin Cruijssen
Gracias a todos por los consejos, los tendré en cuenta cuando jueguen golf en el futuro.
Epicness
0

Mathematica, 28 bytes

Which[#>2#2,#-#2,#==#2,#+1]&
alephalpha
fuente
0

PHP> = 7.1, 51 bytes

for([,$a,$b]=$argv;++$x<2*$a;)$a%$x!=$b?:print$x._;

Versión en línea

Jörg Hülsermann
fuente
0

Axioma, 147128 bytes

g(a:PI,c:PI):Union(List PI,Stream INT)==(a<c=>[];r:=a-c;r=0=>expand((a+1..)::UniversalSegment INT);[b for b in divisors(r)|b>c])

deshazte de él y prueba

--a%b=c return all possible b
f(a:PI,c:PI):Union(List PI, Stream INT)==
    a<c=>[]
    r:=a-c
    r=0=>expand((a+1..)::UniversalSegment INT)
    [b  for b in divisors(r)|b>c]

(3) -> [[i,j,g(i,j)] for i in [5,9,8,6,8,2,8,10] for j in [2,4,2,6,7,4,5,1]]
   (3)
   [[5,2,[3]], [9,4,[5]], [8,2,[3,6]], [6,6,[7,8,9,10,11,12,13,14,15,16,...]],
    [8,7,[]], [2,4,[]], [8,5,[]], [10,1,[3,9]]]
                                                      Type: List List Any

Esto encontraría toda la solución, incluso la solución de conjunto infinito ...

RosLuP
fuente
0

Pip , 9 bytes

a%,a+2@?b

Toma los dos números como argumentos de línea de comandos. Emite la solución más pequeña, o nula si no existe una solución. Pruébalo en línea!

Explicación

           a, b are cmdline args (implicit)
  ,a+2     Range from 0 up to but not including a+2
a%         Take a mod each of those numbers
           (Note that a%0 returns nil; it emits a warning, but only if warnings are turned on)
      @?b  Find the index of the first occurrence of b in this list, or nil if it doesn't occur
           Autoprint (implicit)

Por ejemplo, con entrada de 8y 2:

   a+2   10
  ,      [0 1 2 3 4 5 6 7 8 9]
a%       [() 0 0 2 0 3 2 1 0 8]

El índice basado en 0 de la primera aparición de 2en esta lista es 3, que es nuestra solución.

DLosc
fuente
0

J , 14 bytes

(->]){-,~=*1+]

Pruébalo en línea!

Traducción de la solución Python 2 de Rod .

Cómo funciona

Los raros casos en los que un código J se puede traducir directamente a Python.

(->]){-,~=*1+]  <=>  [(a==b)*(1+b),a-b][a-b>b]
         =*1+]        (a==b)*(1+b)
      -,~            [            ,a-b]
     {                                 [     ]
(->])                                   a-b>b
Bubbler
fuente
0

Perl 6 , 23 bytes

{grep $^a%*==$^b,^$a+2}

Pruébalo en línea!

Bloque de código anónimo que devuelve una lista de posibles valores de 2hastaa+1

Jo King
fuente
0

ORK , 566 bytes

When this program starts:
I have a inputter called I
I have a number called a
I have a number called b
I is to read a
I is to read b
I have a mathematician called M
M's first operand is a
M's second operand is b
M is to subtract
I have a number called n
n is M's result
M's first operand is b
M's second operand is n
M is to compare
I have a scribe called W
If M says it's less then W is to write n
If M says it's less then W is to write "\n"
M's second operand is a
M is to compare
If M says it's equal then W is to write a
If M says it's equal then W is to write a

Pruébalo en línea!

O objetos R K ool. Afortunadamente, sin embargo, no necesité usar ninguno (además de los integrados) para esta tarea.

JosiahRyanW
fuente
0

F #, 40 bytes

let m a b=Seq.find(fun x->a%x=b){1..a+1}

Pruébalo en línea!

Muy claro. Lanza un System.Collections.Generic.KeyNotFoundExceptionsi no se puede encontrar una solución.

También puede modificarlo Seq.tryFind, lo que devolverá un int option, con Nonesi no se puede encontrar una solución.

Ciaran_McCarthy
fuente
0

> <> , 21 bytes

El mismo truco que la mayoría de las soluciones publicadas. Primero, preparamos todos los valores necesarios en la pila y luego verificamos las comparaciones.

::r::{-:{)?nr=?!;1+n;

Pruébalo en línea!

PidgeyUsedGust
fuente
0

Whispers v2 , 128 bytes

> Input
> Input
>> 1²
>> (3]
>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7
>> L⋅R
>> Each 9 4 8
> {0}
>> {10}
>> 12∖11
>> Output 13

Pruébalo en línea!

Devuelve un conjunto de todas las soluciones posibles y el conjunto vacío (es decir, ) cuando no existe una solución.

Cómo funciona

Como era de esperar, funciona casi de manera idéntica a la mayoría de las otras respuestas: genera una lista de números y verifica cada módulo inverso con el argumento.

Si está familiarizado con el funcionamiento de la estructura del programa Whispers, siéntase libre de saltar a la línea horizontal. Si no: esencialmente, Whispers funciona en un sistema de referencia línea por línea, comenzando en la línea final. Cada línea se clasifica como una de dos opciones. O es una línea nilad , o es una línea de operador .

Las líneas Nilad comienzan con >, como > Inputo > {0}y devuelven el valor exacto representado en esa línea, es decir, > {0}devuelve el conjunto{0 0}. > Inputdevuelve la siguiente línea de STDIN, evaluada si es posible.

Las líneas de operador comienzan con >>, como >> 1²o >> (3]y denotan ejecutar un operador en uno o más valores. Aquí, los números utilizados no hacen referencia a esos números explícitos, sino que hacen referencia al valor en esa línea. Por ejemplo, ²es el comando cuadrado (nortenorte2), por lo >> 1²que no devuelve el valor12, en su lugar, devuelve el cuadrado de la línea 1 , que, en este caso, es la primera entrada.

Por lo general, las líneas de operador solo funcionan usando números como referencias, aunque puede haber notado las líneas >> L=2y >> L⋅R. Estos dos valores, Ly R, se usan junto con Eachdeclaraciones. Eachlas declaraciones funcionan tomando dos o tres argumentos, nuevamente como referencias numéricas. El primer argumento (p 5. Ej. ) Es una referencia a una línea de operador que utiliza una función, y el resto de los argumentos son matrices. Luego iteramos la función sobre la matriz, donde el LyR en la función representan los elementos actuales en las matrices que se repiten. Como ejemplo:

Dejar UN=[1,2,3,4 4], si=[4 4,3,2,1] y F(X,y)=X+y. Suponiendo que estamos ejecutando el siguiente código:

> [1, 2, 3, 4]
> [4, 3, 2, 1]
>> L+R
>> Each 3 1 2

Luego obtenemos una demostración de cómo Eachfuncionan las declaraciones. Primero, cuando trabajamos con dos matrices, las comprimimos para formarC=[(1,4 4),(2,3),(3,2),(4 4,1)] luego mapa F(X,y) sobre cada par, formando nuestra matriz final re=[F(1,4 4),F(2,3),F(3,2),F(4 4,1)]=[5 5,5 5,5 5,5 5]

Pruébalo en línea!


Cómo funciona este código

Trabajando de forma contraria a la forma en que funciona Whispers, partimos de las dos primeras líneas:

> Input
> Input

Esto recopila nuestras dos entradas, digamos X y y, y los almacena en las líneas 1 y 2 respectivamente. Luego almacenamosX2en la línea 3 y crea un rangoUN: =[1...X2]en la línea 4 . A continuación, saltamos a la sección.

>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7

Lo primero que se ejecuta aquí es la línea 7 , >> Each 5 4que itera línea 5 al borde 4 . Esto produce la matrizsi: =[yo%XEl |yoUN], dónde un%sise define como el módulo deun y si.

A continuación, ejecutamos la línea 8 , >> Each 6 7que itera línea 6 sobresi, produciendo una matriz C: =[(yo%X)=yEl |yoUN].

Para las entradas X=5 5,y=2, tenemos UN=[1,2,3,...,23,24,25], si=[0 0,1,2,1,0 0,5 5,5 5,...,5 5,5 5] y C=[0 0,0 0,1,0 0,0 0,...,0 0,0 0]

Luego saltamos a

>> L⋅R
>> Each 9 4 8

que es nuestro ejemplo de una Eachdeclaración diádica . Aquí, nuestra función es la línea 9, es decir, >> L⋅Ry nuestras dos matrices sonUN y C. Multiplicamos cada elemento enUN con su elemento correspondiente en C, que produce una matriz, mi, donde cada elemento funciona a partir de la siguiente relación:

miyo={0 0Cyo=0 0UNyoCyo=1

Luego terminamos con una matriz que consiste en 0 0sy los módulos inversos de X y y. Para eliminar el0 0s, convertimos esta matriz en un conjunto ( >> {10}), luego tomamos la diferencia de conjunto entre este conjunto y{0 0}, produciendo, luego produciendo, nuestro resultado final.

caird coinheringaahing
fuente
-1

C #, 53 bytes (83 con encabezado de función)

static int F(int a, int b){
    for(int i=1;i<=a+1;i++){if(a%i==b)return i;}return 0;
}

Pruébalo en línea

Primero prueba en codegolf. Probablemente no sea el mejor lenguaje para usar, ni la codificación más eficiente.

Alex
fuente
55
Elimine los espacios en blanco innecesarios para ahorrar unos 10 o más bytes
Sr. Xcoder