Calcular o módulo inverso

18

A tarefa:

Emita um valor para x, onde a mod x = bpara dois valores fornecidos a,b.

Suposição

  • ae bsempre serão inteiros positivos
  • Nem sempre haverá uma solução para x
  • Se existirem várias soluções, produza pelo menos uma delas.
  • Se não houver soluções, não produza nada ou alguma indicação de que não existem soluções.
  • Incorporados são permitidos (não tão divertidos quanto outras abordagens matemáticas)
  • As saídas são sempre números inteiros

Exemplos

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

Isso é , então os bytes mais baixos vencem.

Graviton
fonte
Pode ocorrer erro se nenhuma solução for encontrada?
clap
@ConfusedMr_C Tecnicamente, isso indica que não há solução, então sim.
Graviton 17/05

Respostas:

11

JavaScript , 28 27 26 24 23 bytes

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

Experimente online!

false indica nenhuma solução.

-1 graças @Arnauld

eush77
fonte
Bem feito e bem jogado.
Shaggy
Então, para chamá-lo, você precisa dar um nome à função externa, digitar f=...e depois chamar f(8)(3)? Isso parece um pouco barato? A maneira normal de chamar uma função seria f(8,3), o que tornaria sua definição de função mais longa?
Steve Bennett
3
@SteveBennett True, a definição é curry , o que significa que deve ser chamada assim (8)(3), mas há um consenso sobre o PPCG que é permitido . Você não precisa dar um nome a ele.
Eush77
1
@SteveBennett É divertido como você acha que 26 vs -15 é tudo, menos um consenso claro. Boa sorte tentando disputar.
Eush77
1
@SteveBennett, como 55 para 1 é um consenso fraco?
Cyoce 24/05
6

MATL , 6 bytes

tQ:\=f

Experimente online! Ou verifique todos os casos de teste .

Explicação

Considere entradas 8, 2como um exemplo.

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
fonte
4

Gelatina , 5 bytes

‘R⁸%i

Retorna o mínimo válido x ou 0 se não houver nenhum.

Experimente online!

Dennis
fonte
3

Groovy, 48 bytes (usando interno):

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

Eval.me(...+"g") - Afixa "g" à entrada, tornando-a um BigInteger.

modInverse(...) - Executa a operação do módulo inverso.


Java 8, 70 bytes

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

R , 33 28 bytes

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

Experimente online!

-4 bytes graças a Jarko Dubbeldam.

-1 byte graças a Giuseppe.

Retorna NAse não houver solução. O TIO não possui a biblioteca pryr instalada; portanto, o código nesse link é usado function(a,b).

Nitrodon
fonte
pryr::f(which(a%%1:(a+1)==b)) é 4 bytes mais curto.
JAD 17/05
você também pode eliminar outro byte usando match(b,a%%1:(a+1)), que retorna NApara um valor ausente.
Giuseppe
1

Geléia , 11 10 bytes

³%_⁴
r‘ÇÐḟ

Um programa completo usando os dois números inteiros positivos ae b, e imprimindo uma lista das soluções inteiras entre min(a,b)+1e max(a,b)+1inclusive.

Experimente online!

Jonathan Allan
fonte
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

Resultado:

{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
fonte
Ao usar esses operadores ASCII estendidos em um formato binário, eles precisam de um espaço na frente ao serem definidos, caso contrário, o analisador gera um erro. Então teria que ser a_ ±b_. Mas é mais curto de usar em Casesvez de Selectuma função sem nome:Cases[Range[9#],x_/;#~Mod~x==#2]&
Martin Ender
1

Haskell , 33 bytes

Falha no code.hs: out of memory (requested ??? bytes)caso de não haver solução (o tempo limite do TIO expirou antes):

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

Experimente online!

Obrigado em Ørjan Johansen por detectar um erro!

ბიმო
fonte
Isso fornece respostas erradas para os casos de teste em que se bdivide a.
Ørjan Johansen
1

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

Resposta do Python do Porto de Rod . Graças à WW por -1 byte.

ENORME graças a Kevin Cruijssen por -30 bytes.

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

Experimente online!

Epicness
fonte
1
Bem vindo ao site! Parece que você pode remover o espaço depois return.
Wheat Wizard
Bem-vindo ao PPCG! Para respostas C # não recursivas, é sempre melhor e mais curto usar uma função lambda ( i=>{/*code here*/}). Nesse caso, no entanto, como você tem 2 entradas, pode ser uma função lambda de curry salvar um byte adicional (em a=>b=>{/*code here*/}vez de (a,b)=>{/*code here*/}). Além disso, você pode remover os parênteses em torno de suas verificações de if. No total, sem alterar nenhuma das suas funcionalidades, ele se torna a=>b=>a-b>b?a-b:a==b?a+1:0 26 bytes
Kevin Cruijssen #
Além disso, se você ainda não o viu, pode ser interessante ler dicas de golfe em <todos os idiomas> e dicas de golfe em C # . Aproveite sua estadia! :)
Kevin Cruijssen
Obrigado a todos pelas dicas, vou ter isso em mente quando jogar golfe no futuro.
Epicness
0

Mathematica, 28 bytes

Which[#>2#2,#-#2,#==#2,#+1]&
alefalpha
fonte
0

PHP> = 7.1, 51 bytes

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

Versão Online

Jörg Hülsermann
fonte
0

Axioma, 147 128 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])

ungolf-lo e testar

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

Isso encontraria toda a solução, mesmo a solução de conjunto infinito ...

RosLuP
fonte
0

Pip , 9 bytes

a%,a+2@?b

Toma os dois números como argumentos da linha de comando. Produz a menor solução, ou nulo se não houver solução. Experimente online!

Explicação

           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 exemplo, com entrada de 8e 2:

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

O índice baseado em 0 da primeira ocorrência 2desta lista é 3: qual é a nossa solução.

DLosc
fonte
0

J , 14 bytes

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

Experimente online!

Tradução da solução Rod's Python 2 .

Como funciona

Os casos raros em que um código J pode ser traduzido diretamente para Python.

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

Japonês , 13 bytes

UµV ?U>V©U:ÒV

Experimente online!

Tradução da solução JS de eush77 .

O código é justamente (U-=V)?U>V&&U:-~Vquando transpilado para JS, onde Ue Vsão os dois valores de entrada.

Bubbler
fonte
0

Japonês , 7 bytes

(Eventualmente) Saídas undefinedse não houver solução.

@%X¥V}a

Experimente aqui

Shaggy
fonte
0

Perl 6 , 23 bytes

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

Experimente online!

Bloco de código anônimo que retorna uma lista de valores possíveis de 2atéa+1

Brincadeira
fonte
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

Experimente online!

O bjeta R K ool. Felizmente, no entanto, não precisei usar nenhum (além dos incorporados) para esta tarefa.

JosiahRyanW
fonte
0

F #, 40 bytes

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

Experimente online!

Bem direto. Lança a System.Collections.Generic.KeyNotFoundExceptionse nenhuma solução puder ser encontrada.

Você também pode modificá-lo para Seq.tryFind, que retornará um int option, com Nonese nenhuma solução puder ser encontrada.

Ciaran_McCarthy
fonte
0

> <> , 21 bytes

Mesmo truque que a maioria das soluções publicadas. Primeiro, preparamos todos os valores necessários na pilha e depois checamos as comparações.

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

Experimente online!

PidgeyUsedGust
fonte
0

Sussurros 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

Experimente online!

Como funciona

Sem surpresa, ele funciona quase de forma idêntica à maioria das outras respostas: gera uma lista de números e verifica cada um quanto ao módulo inverso com o argumento.

Se você estiver familiarizado com o funcionamento da estrutura do programa Whispers, fique à vontade para pular para a linha horizontal. Caso contrário: essencialmente, o Whispers funciona em um sistema de referência linha por linha, iniciando na linha final. Cada linha é classificada como uma das duas opções. Ou é uma linha sem linha ou é uma linha de operador .

As linhas Nilad começam com >, como > Inputou, > {0}e retornam o valor exato representado nessa linha, ou seja, > {0}retorna o conjunto{0 0}> Input

>>>> 1²>> (3]²nn2>> 1²12

Geralmente, as linhas do operador funcionam apenas usando números como referências, mas você pode ter notado as linhas >> L=2e>> L⋅R . Esses dois valores Le Rsão usados ​​em conjunto com Eachinstruções. EachAs instruções funcionam usando dois ou três argumentos, novamente como referências numéricas. O primeiro argumento (por exemplo 5) é uma referência a uma linha de operador que utiliza uma função, e o restante dos argumentos são matrizes. Em seguida, iteramos a função sobre a matriz, onde a Le Rna função representam os elementos atuais nas matrizes que estão sendo iteradas. Como um exemplo:

UMA=[1,2,3,4]B=[4,3,2,1]f(x,y)=x+y

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

EachC=[(1,4),(2,3),(3,2),(4,1)]f(x,y)D=[f(1,4),f(2,3),f(3,2),f(4,1)]=[5,5,5,5]

Experimente online!


Como este código funciona

Trabalhando contra-intuitivamente como o Whispers funciona, começamos pelas duas primeiras linhas:

> Input
> Input

xyx2UMA: =[1...x2]

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

>> Each 5 4B: =[Eu%x|EuUMA]uma%bumab

>> Each 6 7BC: =[(Eu%x)=y|EuUMA]

x=5,y=2UMA=[1,2,3,...,23,24,25]B=[0 0,1,2,1,0 0,5,5,...,5,5]C=[0 0,0 0,1,0 0,0 0,...,0 0,0 0]

Em seguida, pulamos para

>> L⋅R
>> Each 9 4 8

Each>> L⋅RUMACUMACE

EEu={0 0CEu=0 0UMAEuCEu=1

0 0xy0 0>> {10}{0 0}

caird coinheringaahing
fonte
-1

C #, 53 bytes (83 com cabeçalho de função)

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

Experimente Online

Primeira tentativa no codegolf. Provavelmente não é o melhor idioma para usar, nem a codificação mais eficiente.

Alex
fonte
5
Remover o espaço em branco desnecessário economizar cerca de 10 ou mais bytes
Mr. Xcoder