Задача заключается в следующем. Дано целое число x(например , что по xмодулю 100000000003не равно 0) представлены коду в любом случае вы найдете удобными, выходное другое целое число , y < 100000000003так что (x * y) mod 100000000003 = 1.

Ваш код должен занять менее 30 минут для запуска на стандартном настольном компьютере для любого ввода, xтакого как |x| < 2^40.

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

Вход: 400000001. Выход: 65991902837

Ввод: 4000000001. Выход: 68181818185

Вход: 2. Выход: 50000000002

Вход: 50000000002. Выход: 2.

Вход: 1000000. Выход: 33333300001

ограничения

Вы не можете использовать какие-либо библиотеки или встроенные функции, выполняющие арифметику по модулю (или эту обратную операцию). Это означает, что вы даже не можете обойтись a % bбез реализации %себя. Однако вы можете использовать все другие встроенные функции без модуля арифметики.

Подобный вопрос

Это похоже на этот вопрос, хотя, надеюсь, достаточно отличается, чтобы все еще представлять интерес.

Pyth, 24 байта

L-b*/bJ+3^T11Jy*uy^GT11Q

Тестирование

Это использует тот факт, что ^ (р-2) мод р = а ^ -1 мод р.

Во-первых, я вручную переопределяю модуль, для конкретного случая мода 100000000003. Я использую формулу a mod b = a - (a/b)*b , где /находится этажное деление. Я генерирую модуль с 10^11 + 3помощью кода +3^T11, затем сохраняю его J, затем использую эту и приведенную выше формулу для вычисления b mod 100000000003 с -b*/bJ+3^T11J. Эта функция определяется как yс L.

Далее я начинаю со входа, затем поднимаю его до десятой степени и уменьшаю мод до 100000000003, и повторяю это 11 раз. y^GTкод, выполняемый на каждом шаге, и uy^GT11Qзапускает его 11 раз, начиная с ввода.

Теперь у меня есть Q^(10^11) mod 10^11 + 3, и я хочуQ^(10^11 + 1) mod 10^11 + 3 , поэтому я умножить на вход с *, уменьшить его мод 100000000003 с yодним последним разом, и вывод.

Haskell , 118 113 105 101 байт

Вдохновлен этим решением .

-12 от Орьяна Йохансена

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

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

Haskell , 48 байтов

Переписать это решение . Хотя это решение достаточно быстрое для тестового вектора, оно слишком медленное для других входов.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

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

Брахилог , 22 байта

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

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

Это заняло около 10 минут для 1000000немного другой (и более длинной) версии кода, которая была ровно в два раза быстрее (проверял только положительные значения İвместо положительных и отрицательных значений ). Поэтому для этого ввода потребуется около 20 минут.

объяснение

Мы просто опишем это Input × Output - 1 = 100000000003 × an integer, и пусть арифметика ограничения найдет Outputдля нас.

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

Технически нам не нужна явная маркировка ≜, однако, если мы ее не используем, ~×мы не будем проверять регистр N = [100000000003,1](потому что он часто бесполезен), что означает, что это будет очень медленно для ввода, 2например, потому что ему нужно будет найти второе наименьшее целое число вместо первого.

Python, 53 51 49 58 53 49 байтов

-2 байта благодаря orlp
-2 байта благодаря officialaimm
-4 байта благодаря Фелипе Нарди Батисту
-3 байта благодаря isaacg
-1 байту благодаря Орджану Йохансену
-2 байта благодаря Федерико Полони

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

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

Мне потребовалось ~ 30 минут, чтобы понять это. Мое решение состоит в том, чтобы начать с первого числа, которое изменится на 1. Это число равно 1. Если оно делится на x, то y это число, деленное на x. Если нет, добавьте 10000000003 к этому номеру, чтобы найти второе число, мод 1000000003 будет равен 1, и повторите.

JavaScript (ES6), 153 143 141 байт

Вдохновлен этим ответом от math.stackexchange.com .

Рекурсивная функция, основанная на евклидовом алгоритме.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

Модуль по модулю реализуется с помощью вычислений:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Поскольку коэффициент также необходим, то делать это таким образом действительно имеет смысл.

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

let f =

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

console.log(f(2))
console.log(f(50000000002))
console.log(f(1000000))

C ++ 11 (GCC / Clang, Linux), 104 102 байта

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Ungolfed, основанный на теореме Эйлера и двоичном возведении в степень.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}

Mathematica, 49 байтов

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&

PHP, 71 байт

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Testcases

Рубин , 58 байт

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

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

Текущая версия перебором, которая составляет 47 байт , но может быть это слишком медленно:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

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