Ваша задача - дать два целых числа aи bвычислить модульную мультипликативную инверсию по модулю b, если она существует.

Модульная обратная по aмодулю bэто число cтакое, что ac ≡ 1 (mod b). Это число является уникальным по модулю bдля любой пары aи b. Он существует, только если наибольшим общим делителем aи bявляется 1.

Страницу Wikipedia для модульного мультипликативного обратного можно обратиться , если вам необходима дополнительная информация о теме.

Вход и выход

Входные данные задаются либо двумя целыми числами, либо списком из двух целых чисел. Ваша программа должна выводить либо одно число, либо модульную мультипликативную инверсию, которая находится в интервале 0 < c < b, либо значение, указывающее, что инверсии нет. Значение может быть любым, кроме числа в диапазоне (0,b), а также может быть исключением. Однако значение должно быть одинаковым для случаев, когда нет обратного.

0 < a < b можно предположить

правила

Программа должна завершиться в какой-то момент и решить каждый контрольный пример менее чем за 60 секунд.
Применяются стандартные лазейки

Контрольные примеры

Тестовые случаи ниже приведены в формате, a, b -> output

1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist

счет

Это кодовый гольф, поэтому выигрывает самый короткий код для каждого языка.

Это и это схожие вопросы, но оба задают конкретные ситуации.

code-golf math number number-theory abstract-algebra Халвард Хаммель
источник

6

Из Маленькой теоремы Ферма следует, что мультипликативная обратная a, если она существует, может быть эффективно вычислена как ^ (phi (b) -1) mod b, где phi - это функция Эйлера: phi (p0 ^ k0 * p1 ^ k1 * ...) = (p0-1) * p0 ^ (k0-1) * (p1-1) * p1 ^ (k1-1) * ... Не говорю, что это приводит к сокращению кода :)

ngn

1

@Jenny_mathy Дополнительный ввод обычно запрещен.

г-н Xcoder

3

Я считаю шесть ответов, которые кажутся грубыми и маловероятными, чтобы выполнить все контрольные примеры за 60 секунд (некоторые из них сначала выдают ошибку стека или памяти).

Орджан Йохансен

1

@ngn: Вы связали маленькую теорему Ферма (FLT) с улучшением Эйлера. Ферма не знал о функции Фи Эйлера. Кроме того, улучшение FLT и Эйлера применимо, только если gcd (a, b) = 1. Наконец, в написанной вами форме, «a ^ (\ phi (b) -1) mod b» конгруэнтен 1, а не a ^ (- 1). Чтобы получить ^ (- 1), используйте мод ^ (\ phi (b) -2) b.

Эрик Тауэрс

1

@EricTowers Эйлера является следствием. Относительно "gcd (a, b) = 1" - я действительно сказал, "если это [обратное] существует". Вы уверены, что о фи (б) -2?

СПП

11

Mathematica, 14 байтов

Обязательный Mathematica встроен :

ModularInverse

Это функция, которая принимает два аргумента ( aи b) и возвращает инверсию мода b, если он существует. Если нет, возвращается ошибка ModularInverse: a is not invertible modulo b..

Tutleman
источник

7

JavaScript (ES6), 79 73 62 61 байт

Возвращает, falseесли обратного не существует.

Он использует расширенный евклидов алгоритм и решает все тестовые случаи практически мгновенно.

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

Контрольные примеры

Показать фрагмент кода

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

console.log(f(1, 2)) // -> 1
console.log(f(3, 6)) // -> Does not exist
console.log(f(7, 87)) // -> 25
console.log(f(25, 87)) // -> 7
console.log(f(2, 91)) // -> 46
console.log(f(13, 91)) // -> Does not exist
console.log(f(19, 1212393831)) // -> 701912218
console.log(f(31, 73714876143)) // -> 45180085378
console.log(f(3, 73714876143)) // -> Does not exist

Expand snippet

Arnauld
источник

Почему невозможно написать имя функции f, например, в f (c, a, b = 0, d = 1, n = a) => c? F (a% c, c, d, b- ( aa% c) / c * d, n): a <2 && (b + n)% n?

Рослуп

@RosLup f(x,y)всегда анализируется как вызов функции, за исключением случаев, когда ему явно предшествует functionключевое слово. С другой стороны, анонимная функция стрелки объявляется как (x,y)=>somethingи f=(x,y)=>somethingприсваивает функцию fпеременной.

Arnauld

4

Желе , 2 байта

æi

Попробуйте онлайн!

Он использует встроенную функцию для модульной инверсии и возвращает 0 для отсутствия модульной инверсии.

Желе , 7 байт

R×%⁸’¬T

Попробуйте онлайн!

Выводит пустой набор (представленный в виде пустой строки) без модульной инверсии. Запускается нехватка памяти на TIO для самых больших тестовых случаев, но должна работать при достаточном объеме памяти.

Как это работает

R×%⁸’¬T  
R        Generate range of b
 ×       Multiply each by a
  %⁸     Mod each by b
    ’    Decrement (Map 1 to 0 and all else to truthy)
     ¬   Logical NOT
      T  Get the index of the truthy element.

Если вы хотите работать с большими тестовыми примерами, попробуйте эту (относительно безвкусицу) версию, которая требует больше времени, чем памяти:

Желе, 9 байт

×⁴%³’¬ø1#

Попробуйте онлайн!

Как это работает

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy

fireflame241
источник

4

Python 2 , 34 байта

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

Попробуйте онлайн!

Рекурсивная функция , которая дает Trueдля print f(1,2), который я считаю приемлемыми, и ошибки для недействительных входов.

$x$ $a\cdot x\equiv 1\pmod{b}$

$a\cdot x-1=k\cdot b$ $k$

Взятие $\mod{a}$ $-1\equiv k\cdot b\pmod{a}$ $-k\cdot b\equiv1\pmod{a}$ $k$

$k$ $f(-b\%a,a)$

$a$ $a$ $b$

$k$ $a\cdot x-1=k\cdot b$ $x$ $\frac{k\cdot b+1}{a}$

Kritixi Lithos
источник

3

R + числа , 15 байтов

numbers::modinv

возвращается NAдля тех, кто aбез инверсий мод b.

R-Fiddle, чтобы попробовать это!

R , 33 байта (не конкурирует)

Это приведет к ошибке очень большого размера, bпоскольку фактически создает вектор 32*bбитов размера .

function(a,b)which((1:b*a)%%b==1)

Попробуйте онлайн!

Возвращает integer(0)(пустой список) для тех aбез инверсии мод b.

Giuseppe
источник

3

Mathematica, 18 байт

PowerMod[#,-1,#2]&

вход

[31, 73714876143]

J42161217
источник

3

Python 2 , 51 49 54 53 51 49 байт

^{-1 байт благодаря officialaimm}
^{-1 байт благодаря Shaggy}

a,b=input()
i=a<2
while(a*i%b-1)*b%a:i+=1
print+i

Попробуйте онлайн!

Печатает, 0когда нет решения.

прут
источник

1

Выходы 0для a=1и b=2; из тестовых случаев, он должен выводить 1.

Лохматый

Как рекурсивный алгоритм

г-н Xcoder

1

Как указал Шегги, не удается2, 1

г-н Xcoder

@ Шагги должен работать сейчас

Род

Это не возвращает ответ в течение 60 секунд (на TIO) для ввода 31,73714876143.

Ильмари

3

Japt , 9 8 байт

Принимает входные данные в обратном порядке. Выходы -1не совпадают. Вылетает, когда большее целое становится больше.

Ç*V%UÃb1

Попробуй это

Сохранено 1 байт благодаря ETH, указывающему на ошибочное и очень очевидное пространство.

мохнатый
источник

Тестовый ввод, 73714876143,31похоже, вызывает ошибку нехватки памяти в Firefox (и приводит к сбою Chromium). Я не думаю, что это правильный ответ.

Илмари

@IlmariKaronen: Я четко указал на этот факт в своем решении. Мы можем предполагать бесконечную память для целей гольф-кода, поэтому проблемы с памятью и сбои не лишают законной силы это решение.

Лохматый

1

К сожалению, из-за проблем с памятью также невозможно определить, действительно ли ваш код решит тестовые случаи за 60 секунд, как это предусмотрено задачей. Я подозреваю, что этого не произойдет, даже если бы было достаточно памяти, чтобы она не зависала, но без компьютера, который действительно мог бы долго запускать программу, невозможно точно сказать.

Ильмари

2

Python 3 + gmpy , 23 байта

Я не думаю, что это может стать немного короче в Python.

gmpy.invert
import gmpy

Попробуйте онлайн! (не будет работать, если у вас не установлен gmpy)

Мистер Xcoder
источник

2

Python 3 , 49 байт

lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1

Попробуйте онлайн!

Python 3 , 50 байт

lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]

Попробуйте онлайн!

Это бросает IndexError: list index out of rangeв случае, если нет модульного мультипликативного обратного, как это разрешено правилами.

Мистер Xcoder
источник

Это не может вернуть результат для ввода 31,73714876143в течение 60 секунд (на TIO).

Ильмари

@IlmariKaronen Похоже, что финиширует на моей машине за 56 секунд (Macbook Pro '15)

г-н Xcoder

2

8 , 6 байтов

Код

invmod

объяснение

invmodявляется восьмым словом, которое вычисляет значение, обратное a, по модулю b. Возвращается nullпри переполнении или других ошибках.

Использование и тестовые случаи

ok> 1 2 invmod .
1
ok> 3 6 invmod .
null
ok> 7 87 invmod .
25
ok> 25 87 invmod .
7
ok> 2 91 invmod .
46
ok> 13 91 invmod .
null
ok> 19 1212393831 invmod .
701912218
ok> 31 73714876143 invmod .
45180085378
ok> 3 73714876143 invmod .
null

Chaos Manor
источник

2

Пари / ГП , 22 байта

a->b->lift(1/Mod(a,b))

Выдает ошибку, когда нет обратного.

Попробуйте онлайн!

alephalpha
источник

2

J , 28 байт

4 :'(1=x+.y)*x y&|@^<:5 p:y'

Попробуйте онлайн!

Использует теорему Эйлера . Возвращает 0, если обратное не существует.

объяснение

4 :'(1=x+.y)*x y&|@^<:5 p:y'  Input: a (LHS), b (RHS)
4 :'                       '  Define an explicit dyad - this is to use the special
                              form `m&|@^` to perform modular exponentiation
                          y   Get b
                      5 p:    Euler totient
                    <:        Decrement
             x                Get a
                   ^          Exponentiate
               y&|@             Modulo b
       x+.y                   GCD of a and b
     1=                       Equals 1
            *                 Multiply

миль
источник

2

Pyth , 10 байт

3 байта сохранены благодаря @Jakube .

xm%*szdQQ1

Попробуй это здесь!

Возвращает -1без мультипликативного обратного.

Разбивка кода

xm%*szdQQ1      Let Q be the first input.
 m      Q       This maps over [0 ... Q) with a variable d.
   *szd         Now d is multiplied by the evaluated second input.
  %    Q        Now the remained modulo Q is retrieved.
x        1      Then, the first index of 1 is retrieved from that mapping.

Pyth , 15 13 байт

KEhfq1%*QTKSK

Выдает исключение, если мультипликативного обратного не существует.

Попробуй это здесь!

Pyth , 15 байт

Iq1iQKEfq1%*QTK

Это добавляет много байтов для обработки случая, когда такого числа не существует. Программа может быть значительно сокращена, если этот случай не нужно обрабатывать:

fq1%*QTK

Попробуй это здесь!

Мистер Xcoder
источник

2 байта сохранены сKExm%*QdKK1

Jakube

Или 3 байта, если поменять местами входные данные:xm%*szdQQ1

Jakube

@Jakube Большое спасибо, редактирование!

Мистер Кскодер

Как это работает?

Kritixi Lithos

@ Cowsquack Я добавил совершенно примитивную разбивку кода, но у меня нет времени, чтобы включить полное объяснение. Надеюсь, на данный момент это достаточно ясно, но я постараюсь добавить более полное объяснение в ближайшее время.

г-н Xcoder

1

C (gcc) , 115 байтов

#define L long long
L g(L a,L b,L c,L d){return a?g(b%a,a,d-b/a*c,c):b-1?0:d;}L f(L a,L b){return(g(a,b,1,0)+b)%b;}

Попробуйте онлайн!

Расширенный евклидов алгоритм, рекурсивная версия

C (gcc) , 119 байт

long long f(a,b,c,d,t,n)long long a,b,c,d,t,n;{for(c=1,d=0,n=b;a;a=t)t=d-b/a*c,d=c,c=t,t=b%a,b=a;return b-1?0:(d+n)%n;}

Попробуйте онлайн!

Расширенный евклидов алгоритм, итерационная версия

nwellnhof
источник

1

C (gcc) , 48 110 104 байта

#define f(a,b)g(a,b,!b,1,b)
long g(a,b,c,d,n)long a,b,c,d,n;{a=a?g(b%a,a,d,c-(b-b%a)/a*d):!--b*(c+n)%n;}

Попробуйте онлайн!

Это должно работать со всеми входами (которые подходят в течение длительного времени) в течение 60 секунд.

Редактировать. Я уже злоупотребляю nпеременной, поэтому могу предположить, что gcc вставляет первое присваивание %rax.

ceilingcat
источник

1

Увы, это дает неверные результаты даже для довольно небольших входных данных из-за целочисленного переполнения внутри цикла. Например, f(3,1000001)возвращает 717, что, очевидно, является ерундой (правильный ответ - 333334). Кроме того, даже если бы эта ошибка была исправлена с использованием более широкого целочисленного типа, этот метод грубой силы наверняка истек бы для некоторых из более крупных тестовых случаев, приведенных в задаче.

Ильмари

0

Python 2 + sympy, 74 байта

from sympy import*
def f(a,m):i,_,g=numbers.igcdex(a,m);return g==1and i%m

Попробуйте онлайн!

Взято из исходного кода Jelly.

totallyhuman
источник

0

Аксиома, 45 байт

f(x:PI,y:PI):NNI==(gcd(x,y)=1=>invmod(x,y);0)

0 для ошибки, иначе верните z с x * z Mod y = 1

RosLuP
источник

0

Python 2 , 52 байта

-3 байта благодаря мистеру Xcoder.

f=lambda a,b,i=1:i*a%b==1and i or i<b and f(a,b,i+1)

Попробуйте онлайн!

Выходы Falseна нет решения и ошибок, как bстановится больше.

Встроенный TIO

Я просто тестирую фреймы в Stack Snippets, и они работают просто фантастически.

Показать фрагмент кода

html,body{height:100%;}iframe{height:100%;width:100%;border:none;}

<iframe src="https://tio.run/##PY3BCsIwEETv/Yq5CEndy6ZotbhfIh4SanBB09Lm4tdHU8HTvIHhzfzOjym5UqI8/SuMHp4CqfCgrd8FEfZphGJaoJeAWqLZJnu2Jd/XvEJwNUxwlmA6wrFmTzj1FdzhT4QzV@DuR7emidULTdhMA@ZFU/4@tGrLBw"></iframe>

Expand snippet

totallyhuman
источник

Я не уверен, что это работает, не может i*a%bбыть 0?

Пшеничный волшебник

Сбой с ошибкой «превышена максимальная глубина рекурсии» для ввода (31,73714876143).

Ильмари

0

JavaScript (ES6), 42 41 39 38 байт

Выходы falseне совпадают. Выдает ошибку переполнения, поскольку второе число становится слишком большим.

x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)

мохнатый
источник

0

Желе , 27 байт

²%³
⁴Ç⁹Ð¡x⁸
ÆṪ’BṚçL$P%³×gỊ¥

Попробуйте онлайн!

Используется теорема Эйлера с модульным возведением в степень. Поскольку у Jelly нет встроенной функции для модульного возведения в степень, его необходимо было реализовать, и он занял большую часть байтов.

миль
источник

0

Аксиома, 99 байт

w(a,b,x,u)==(a=0=>(b*b=1=>b*x;0);w(b rem a,a,u,x-u*(b quo a)));h(a,b)==(b=0=>0;(b+w(a,b,0,1))rem b)

он использует функцию h (); h (a, b) возвращает 0, если ошибка [не существует обратного], в противном случае она возвращает z так, что a * z mod b = 1 Это было бы нормально, даже если аргументы отрицательны ...

это будет общая функция egcd (), которая возвращает список int (так что они тоже могут быть отрицательными)

egcd(aa:INT,bb:INT):List INT==
   x:=u:=-1   -- because the type is INT
   (a,b,x,u):=(aa,bb,0,1)
   repeat
      a=0=>break
      (q,r):=(b quo a, b rem a)
      (b,a,x,u):=(a,r,u,x-u*q)
   [b,x, (b-x*aa)quo bb]

вот как это использовать

(7) -> h(31,73714876143)
   (7)  45180085378
                                                    Type: PositiveInteger

Я нахожу базовый алгоритм в Интернете с https://pastebin.com/A13ybryc

RosLuP
источник

Модульный мультипликативный обратный

Вход и выход

правила

Контрольные примеры

счет

Ответы:

Mathematica, 14 байтов

JavaScript (ES6), 79 73 62 61 байт

Контрольные примеры

Желе , 2 байта

Желе , 7 байт

Желе, 9 байт

Python 2 , 34 байта

R + числа , 15 байтов

R , 33 байта (не конкурирует)

Mathematica, 18 байт

Python 2 , 51 49 54 53 51 49 байт

Japt , 9 8 байт

Python 3 + gmpy , 23 байта

Python 3 , 49 байт

Python 3 , 50 байт

8 , 6 байтов

Пари / ГП , 22 байта

J , 28 байт

объяснение

Pyth , 10 байт

Разбивка кода

Pyth , 15 13 байт

Pyth , 15 байт

C (gcc) , 115 байтов

C (gcc) , 119 байт

C (gcc) , 48 110 104 байта

Python 2 + sympy, 74 байта

Аксиома, 45 байт

Python 2 , 52 байта

Встроенный TIO

JavaScript (ES6), 42 41 39 38 байт

Желе , 27 байт

Аксиома, 99 байт