Calcular o inverso de um módulo inteiro 100000000003

21

A tarefa é a seguinte. Dado um número inteiro x(de modo que o xmódulo 100000000003não seja igual a 0) apresentado ao seu código da maneira que achar conveniente, imprima outro número inteiro y < 100000000003para que (x * y) mod 100000000003 = 1.

Seu código deve levar menos de 30 minutos para ser executado em uma máquina desktop padrão para qualquer entrada xcomo essa |x| < 2^40.

Casos de teste

Entrada: 400000001. Saída: 65991902837

Entrada: 4000000001. Saída: 68181818185

Entrada: 2. Saída: 50000000002

Entrada: 50000000002. Saída: 2.

Entrada: 1000000. Saída: 33333300001

Restrições

Você não pode usar nenhuma biblioteca ou função interna que execute módulo aritmético (ou esta operação inversa). Isso significa que você não pode nem ficar a % bsem %se implementar . No entanto, você pode usar todas as outras funções internas aritméticas não modulares.

Pergunta semelhante

Isso é semelhante a essa pergunta, embora seja esperançosamente diferente o suficiente para ainda ser interessante.

isaacg
fonte
Então a- (a / b) * b está bom?
user253751
@immibis Isso parece bem.
tag: código restrito?
Felipe Nardi Batista
1
O que há de especial 100000000003? (me perguntando)
NoOneIsHere
1
@Lembik Nesse caso, você poderia mencionar esse requisito que y <100000000003 na pergunta?
Isaacg

Respostas:

16

Pitão, 24 bytes

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

Suíte de teste

Isso usa o fato de que um ^ (p-2) mod p = a ^ -1 mod p.

Primeiro, reimplemento manualmente o módulo, para o caso específico do mod 100000000003. Uso a fórmula a mod b = a - (a/b)*b, onde /é a divisão com piso. Gero o módulo com 10^11 + 3, usando o código +3^T11, em seguida salve-o e J, em seguida, use esta e a fórmula acima para calcular b mod 100000000003 com -b*/bJ+3^T11J. Esta função é definida como ycom L.

Em seguida, começo com a entrada, depois a levo para a décima potência e reduzo o mod 100000000003 e repito isso 11 vezes. y^GTé o código executado em cada etapa e o uy^GT11Qexecuta 11 vezes, iniciando com a entrada.

Agora eu tenho Q^(10^11) mod 10^11 + 3, e quero Q^(10^11 + 1) mod 10^11 + 3, então multiplico pela entrada com *, reduzo-o mod 100000000003 com yuma última vez e com saída.

isaacg
fonte
Muito bom mesmo!
Eu estou supondo que é tarde demais para mim para apertar-se os casos de teste ....
1
@Lembik Eu faria de qualquer maneira, mas as opiniões podem variar. É o seu desafio, faça com que ele funcione da maneira que você deseja.
Isaacg 04/07
Da maneira como a pergunta está escrita, é possível que você abandone a redução final, embora eu tenha solicitado um esclarecimento sobre a necessidade de um resultado <100000000003.
Ørjan Johansen
9

Haskell , 118 113 105 101 bytes

Inspirado nesta solução .

-12 de Ørjan Johansen

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]

Experimente online!

Haskell , 48 bytes

Uma reescrita desta solução . Embora rápida o suficiente para o vetor de teste, esta solução é muito lenta para outras entradas.

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

Experimente online!

bartavelle
fonte
Impressionante! Gosto da exponenciação pela abordagem quadrática.
Isaacg
A solução mais curta seria algo como Experimente online! mas eu não acho que seu desempenho é aceitável ...
bartavelle
(1) É mais curto para fazer gum operador (e?b)a s|...(2) Se você alternar ae s, em seguida, você pode fazer !um não -Operador e em linha ypara ele. (3) Você pode se livrar do caro wherecom um lasttruque, ao custo de duplicar z. Experimente online!
Ørjan Johansen
Agora, esses são bons truques!
bartavelle
Ah, e |e==0=ase livra dessa duplicação traquina.
Ørjan Johansen
6

Braquilog , 22 bytes

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

Experimente online!

Isso levou cerca de 10 minutos para 1000000uma versão ligeiramente diferente (e mais longa) do código, que era exatamente duas vezes mais rápida (verificou apenas valores positivos em İvez de positivos e negativos). Portanto, isso deve levar cerca de 20 minutos para concluir essa entrada.

Explicação

Simplesmente descrevemos isso Input × Output - 1 = 100000000003 × an integere deixamos que a aritmética da restrição encontre Outputpor nós.

∧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

Tecnicamente, não precisamos da rotulagem explícita ; no entanto, se não a usarmos, não verificaremos o caso N = [100000000003,1](porque geralmente é inútil), o que significa que isso será muito lento para a entrada, 2por exemplo, porque será necessário encontrar o segundo menor inteiro em vez do primeiro.

Fatalizar
fonte
1
Uau, eu nunca esperaria que a aritmética da restrição o fizesse. Impressionante!
Isaacg
1
@isaacg Infelizmente, a velocidade disso depende completamente do valor de İ, portanto isso ainda é muito lento para produtos grandes.
Fatalize 4/17/17
Atualizado a pergunta. Seu código sempre leva menos de 30 minutos?
6

Python, 53 51 49 58 53 49 bytes

-2 bytes graças a orlp
-2 bytes graças a officialaimm
-4 bytes graças a Felipe Nardi Batist
-3 bytes graças a isaacg
-1 byte graças a Ørjan Johansen
-2 bytes graças a Federico Poloni

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

Experimente Online!

Levei ~ 30 minutos para descobrir isso. Minha solução é começar com o primeiro número que será modificado para 1. Esse número é 1. Se é divisível por x, então y é esse número dividido por x. Caso contrário, adicione 10000000003 a este número para encontrar o segundo número que mod 1000000003 será igual a 1 e repita.

Zachary Cotton
fonte
O primeiro número que será modificado para 1 é 1 ...
orlp 04/07
@orlp lol obrigado. Isso me salvou 2 bytes :)
Zachary Algodão
Interessante, no TIO, isso é rápido para todos os casos de teste, mas um toque aleatório no teclado me deu o 421385994tempo limite.
Ørjan Johansen
@ ØrjanJohansen Boa investigação.
1
Se você precisar bapenas uma vez, por que não codificá-lo?
Federico Poloni
5

JavaScript (ES6), 153 143 141 bytes

Inspirado por esta resposta de math.stackexchange.com .

Uma função recursiva baseada no algoritmo euclidiano.

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)

O módulo é implementado pela computação:

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

Como o quociente também é necessário, fazê-lo dessa maneira realmente faz algum sentido.

Casos de teste

Arnauld
fonte
Você só precisa de piso de 64 bits na última ocorrência para que você possa substituir os outros com 0 | X / Y e remover a declaração
Oki
5

C ++ 11 (GCC / Clang, Linux), 104 102 bytes

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, baseado no teorema de Euler e na exponenciação binária.

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;
}
SteelRaven
fonte
O ISO C ++ requer apenas longpelo menos 32 bits, portanto, não pode necessariamente se manter 1e11 + 3. É de 32 bits no Windows x86-64. longé um tipo de 64 bits no x86-64 Linux (e outros sistemas operacionais que usam a SystemV ABI). Portanto, para ser totalmente portátil, você precisará usar o long longque é garantido em pelo menos 64 bits desde o C ++ 11 .
Peter Cordes
__int128_tnão parece ser C ++ padrão, parece ser uma extensão do gcc, seria legal se você declarasse isso como uma linguagem (C ++ 11 + gcc).
Felix Dombek
3
Este não deveria ser um site de especialistas em C ++, eu esperava que ninguém notasse.
precisa saber é o seguinte
O código @PeterCordes golf não precisa ser portátil ou mesmo bem formado, ele só precisa trabalhar em uma implementação.
Aschepler
1
@aschepler: Eu sei, é por isso que eu disse "você iria precisar". Eu pensei que era útil apontar em qual plataforma funcionaria / não funcionaria, caso alguém tentasse e tivesse problemas.
5137 Peter Cordes
4

Mathematica, 49 bytes

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
J42161217
fonte
Quanto tempo leva para executar?
Menos de 0.001s no meu computador (para o caso 2 ^ 40-1)
Keyu Gan
2

PHP, 71 bytes

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

Casos de teste

Jörg Hülsermann
fonte
1

Ruby , 58 bytes

Utiliza a aplicação de isaacg do pequeno teorema de Fermat por enquanto, enquanto termino de cronometrar a solução de força bruta.

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

Versão atual força bruta, que é de 47 bytes, mas pode ser é muito lento:

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

Experimente online!

Value Ink
fonte