Calculer l'inverse d'un module entier 100000000003

21

La tâche est la suivante. Étant donné un entier x(tel que xmodulo 100000000003n'est pas égal à 0) présenté à votre code de la manière qui vous convient, sortez un autre entier y < 100000000003pour que (x * y) mod 100000000003 = 1.

Votre code doit prendre moins de 30 minutes pour s'exécuter sur une machine de bureau standard pour toute entrée de ce xtype |x| < 2^40.

Cas de test

Entrée: 400000001. Sortie: 65991902837

Entrée: 4000000001. Sortie: 68181818185

Entrée: 2. Sortie: 50000000002

Entrée: 50000000002. Sortie: 2.

Entrée: 1000000. Sortie: 33333300001

Restrictions

Vous ne pouvez pas utiliser de bibliothèques ou de fonctions intégrées qui effectuent l'arithmétique modulo (ou cette opération inverse). Cela signifie que vous ne pouvez même pas vous a % bpasser de %votre propre implémentation . Vous pouvez cependant utiliser toutes les autres fonctions intégrées arithmétiques non modulo.

Question similaire

Ceci est similaire à cette question, même si nous l'espérons suffisamment différent pour être toujours intéressant.

isaacg
la source
Donc a- (a / b) * b est bien?
user253751
@immibis Ça a l'air bien.
tag: code restreint?
Felipe Nardi Batista
1
Qu'est-ce qui est spécial 100000000003? (je me demandais juste)
NoOneIsHere
1
@Lembik Dans ce cas, pourriez-vous mentionner cette exigence que y <100000000003 dans la question?
isaacg

Réponses:

16

Pyth, 24 octets

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

Suite de tests

Ceci utilise le fait qu'un ^ (p-2) mod p = un ^ -1 mod p.

Tout d'abord, je réimplémente manuellement le module, pour le cas spécifique du mod 100000000003. J'utilise la formule a mod b = a - (a/b)*b, où /est la division au sol. Je génère le module avec 10^11 + 3, en utilisant le code +3^T11, puis l'enregistre J, puis utilise ceci et la formule ci-dessus pour calculer b mod 100000000003 avec -b*/bJ+3^T11J. Cette fonction est définie comme yavec L.

Ensuite, je commence par l'entrée, puis je la porte à la dixième puissance et je réduis le mod 100000000003, et je répète cela 11 fois. y^GTest le code exécuté à chaque étape, et l' uy^GT11Qexécute 11 fois en commençant par l'entrée.

Maintenant, j'ai Q^(10^11) mod 10^11 + 3, et je veux Q^(10^11 + 1) mod 10^11 + 3, donc je multiplie par l'entrée avec *, le réduit mod 100000000003 yune dernière fois, et la sortie.

isaacg
la source
Très beau effectivement!
Je suppose qu'il est trop tard pour moi de resserrer les cas de test ....
1
@Lembik Je le ferais quand même, mais les opinions peuvent varier. C'est votre défi, faites-le fonctionner comme vous le souhaitez.
isaacg
De la façon dont la question est écrite, il est possible que vous puissiez supprimer la réduction finale, bien que j'ai demandé une clarification si un résultat <100000000003 est requis.
Ørjan Johansen
9

Haskell , 118 113 105 101 octets

Inspiré de cette solution .

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

Essayez-le en ligne!

Haskell , 48 octets

Une réécriture de cette solution . Bien que suffisamment rapide pour le vecteur de test, cette solution est trop lente pour les autres entrées.

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

Essayez-le en ligne!

Bartavelle
la source
Impressionnant! J'aime l'exponentiation par l'approche quadratique.
isaacg
La solution la plus courte serait quelque chose comme Essayez-le en ligne! mais je ne pense pas que ses performances soient acceptables ...
bartavelle
(1) Il est plus court de faire gun opérateur (e?b)a s|...(2) Si vous changez aet que svous pouvez alors faire !un non- opérateur et en ligne y. (3) Vous pouvez vous débarrasser du cher wherepar une lastastuce, au prix d'une duplication z. Essayez-le en ligne!
Ørjan Johansen
Maintenant, ce sont de belles astuces!
Bartavelle
Oh, et |e==0=ase débarrasse de cette duplication embêtante.
Ørjan Johansen
6

Brachylog , 22 octets

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

Essayez-le en ligne!

Cela a pris environ 10 minutes 1000000avec une version légèrement différente (et plus longue) du code qui était exactement deux fois plus rapide (vérifié uniquement les valeurs positives İau lieu de positives et négatives). Par conséquent, cette opération devrait prendre environ 20 minutes.

Explication

Nous décrivons simplement cela Input × Output - 1 = 100000000003 × an integeret laissons l'arithmétique des contraintes Outputnous trouver .

∧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

Techniquement, nous n'avons pas besoin de l'étiquetage explicite , mais si nous ne l'utilisons pas, nous ne vérifierons pas le cas N = [100000000003,1](car il est souvent inutile), ce qui signifie que cela sera très lent pour la saisie 2par exemple car il devra trouver le deuxième plus petit entier au lieu du premier.

Fatalize
la source
1
Wow, je ne me serais jamais attendu à ce que l'arithmétique des contraintes réussisse. Impressionnant!
isaacg
1
@isaacg La vitesse de ceci dépend malheureusement complètement de la valeur de İ, donc c'est encore assez lent pour les gros produits.
Fatalize
Mis à jour la question. Votre code prend-il toujours moins de 30 minutes?
6

Python, 53 51 49 58 53 49 octets

-2 octets grâce à orlp
-2 octets grâce à officialaimm
-4 octets grâce à Felipe Nardi Batist
-3 octets grâce à isaacg
-1 octet grâce à Ørjan Johansen
-2 octets grâce à Federico Poloni

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

Essayez-le en ligne!

Il m'a fallu environ 30 minutes pour comprendre celui-ci. Ma solution est de commencer par le premier nombre qui passera à 1. Ce nombre est 1. Si son divisible par x, alors y est ce nombre divisé par x. Sinon, ajoutez 10000000003 à ce nombre pour trouver le deuxième nombre dont le mod 1000000003 sera égal à 1 et répétez.

Coton Zachary
la source
Le premier nombre qui passera à 1 est 1 ...
orlp
@orlp lol merci. Cela m'a fait gagner 2 octets :)
Zachary Cotton
Intéressant, sur TIO, cela est rapide pour tous les cas de test, mais un claquement de clavier un peu aléatoire m'a donné 421385994ce délai.
Ørjan Johansen
@ ØrjanJohansen Bon détective.
1
Si vous n'avez besoin bqu'une seule fois, pourquoi ne pas le coder en dur?
Federico Poloni
5

JavaScript (ES6), 153 143 141 octets

Inspiré par cette réponse de math.stackexchange.com .

Une fonction récursive basée sur l'algorithme euclidien.

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)

Modulo est implémenté en calculant:

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

Parce que le quotient est également nécessaire, le faire de cette façon est en fait logique.

Cas de test

Arnauld
la source
Vous n'avez besoin que d'un revêtement de sol 64 bits dans la dernière occurrence, vous pouvez donc remplacer les autres par 0 | x / y et supprimer la déclaration
Oki
5

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

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

Non golfé, basé sur le théorème d'Euler et l'exponentation binaire.

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
la source
ISO C ++ ne doit longêtre qu'au moins 32 bits, il ne peut donc pas nécessairement tenir 1e11 + 3. C'est 32 bits sur Windows x86-64. longest un type 64 bits sous Linux x86-64 (et d'autres systèmes d'exploitation qui utilisent le SystemV ABI). Donc, pour être entièrement portable, vous devez utiliser long long, qui est garanti au moins 64 bits depuis C ++ 11 .
Peter Cordes
__int128_tne semble pas être C ++ standard, il semble que ce soit une extension gcc, ce serait cool si vous le déclariez comme un langage (C ++ 11 + gcc).
Felix Dombek
3
Ce n'est pas censé être un site d'experts C ++, j'espérais que personne ne le remarquerait.
SteelRaven
@PeterCordes Code golf n'a pas besoin d'être portable ou même bien formé, il suffit de travailler sur une seule implémentation.
aschepler
1
@aschepler: Je sais, c'est pourquoi j'ai dit "vous auriez besoin". J'ai pensé qu'il était utile de préciser sur quelle plateforme il fonctionnerait / ne fonctionnerait pas, au cas où quelqu'un l'aurait essayé et aurait rencontré des problèmes.
Peter Cordes
4

Mathematica, 49 octets

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
J42161217
la source
Combien de temps cela prend-il pour fonctionner?
Moins de 0,001s sur mon ordinateur (pour le cas 2 ^ 40-1)
Keyu Gan
2

PHP, 71 octets

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

Cas de test

Jörg Hülsermann
la source
1

Rubis , 58 octets

Utilise l'application isaacg du petit théorème de Fermat pour l'instant pendant que je termine le chronométrage de la solution de force brute.

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

Version actuelle force brute, qui est de 47 octets , mais peut - être est trop lent:

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

Essayez-le en ligne!

Encre de valeur
la source