Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Retour

Résumé de la discussion

Franky1103
10-11-2017 11:53:05

Merci scarta pour ces explications qui sont très claires.

scarta
10-11-2017 08:42:51

La méthode par unité tronquée marche, oui.
Ça ne veut pas dire qu'elle est simple!
Elle ne sert pas à calculer un modulo, mais simplement de savoir si un nombre divise un autre.
Là, avec 10^100 et 1303, oui tu trouve très vite que ça n'est pas divisible mais bon c'est normal smile
Ensuite, 1303 - (1303*7-1)/10 = 391, donc 10^100+1
=> 10^99+391
=> 10^98 + 39 + 391 = 10^98 + 430
=> 10^97 + 43
=> 10^96 + 4 + 1173 etc..
Au final il te faudra 100 (n) étapes, pour chacun des 1303 (p) entiers considérés. C'est très long, c'est en n*p.

La méthode FastPow et PTF peut se faire même à la main
1) tu prends n % (p-1) au lieu de n. Ça fera toujours des calculs en moins (PTF)
2) pour faire q^n modulo p, tu fais
- (q*q modulo p)^(n/2) modulo p si n est pair
- ou q fois ça si n est impair
10^1000000 mod 1302
=> 64 au lieu de 1000000
==> 10^64
==> 100^32
==> 10000^16 = 879^16 (puisqu'en modulo 1303)
==> 1265^8
==> 141^4
==> 336^2
==> 838^1 = 838

Donc 10^1000000 = 838 modulo 1303, et 10^1000000 + 465 est un multiple de 1303.
Tu passes de p*n opérations à log2(p-2) opérations au pire


Je rajoute un lien wikipédia:
https://fr.wikipedia.org/wiki/Exponentiation_modulaire
et aussi que FastPow n'est apparemment pas un nom officiel (c'est juste celui que je donne à chaque fois à ma méthode...)

enigmatus
09-11-2017 21:15:08

J'ai corrigé mon message #10.

Franky1103
09-11-2017 20:49:32

Merci à tous pour votre implication, mais comme tout vieux, je ne connais ni fastpow ni python. Je rêvais d'une solution s'appuyant sur un théorème d'arithmétique modulaire (Fermat ou autre) donnant un résultat "manuel" rapidement. En effet, à priori, sans vraiment la connaitre, la méthode dite par unité tronqué semblait bien s"appliquer à 10^n puisque ce nombre est facile à tronquer et ses chiffres faciles à ajouter.

enigmatus
09-11-2017 20:20:03

Je viens de découvrir qu'en python, il existe une fonction, très rapide, qui fait le boulot :

Code:

print( pow(10,1000000,1303) )

https://en.wikibooks.org/wiki/Algorithm … nentiation

scarta
09-11-2017 17:00:07

La magie du O(ln) big_smile
Et du PTF

enigmatus
09-11-2017 15:14:04

scarta #9 a écrit:

Tu peux regarder pour 1302? C'est le pire cas normalement

Résultat=10, en 0,02 seconde aussi

Édité : Le bon résultat est 718. J'ai cru comprendre que ton algorithme suppose que le nombre p est premier.

scarta
09-11-2017 13:53:28

Tu peux regarder pour 1302? C'est le pire cas normalement

enigmatus
09-11-2017 13:47:11

@scarta : J'ai programmé en python l'algorithme que tu donnes en #6 (il manque le %mod à la fin de la dernière ligne)

Code:

import sys
n=int(sys.argv[1])
p=int(sys.argv[2])

def function(n,p): return PowMod(10,n,p) if n<p else PowMod(10,n%(p-1),p)

def PowMod(base,exp,mod):
   if exp==0: return 1
   Base2=(base*base)%mod
   ret = PowMod(Base2,exp>>1,mod)
   if exp & 1: return (base * ret)%mod
   else:       return ret

print(function(n,p))

Très rapide en effet : pour n=1000000000 et p=1303, résultat=788, obtenu en 0,02 seconde

scarta
09-11-2017 13:02:55

En c#

Code:

using System;
public class MainClass {
  public static void Main(string[] args) {
  long n=1000000000;
  long p=1303;
  if(n>p) n%=p-1;
  Console.WriteLine(FPM(10,n,p));
  }
  public static long FPM(long b, long e, long m)
  {
    if(e==0) return 1;
    long b2=(b*b)%m;
    if((e&1)==0) return FPM(b2, e>>1, m);
    return (b*FPM(b2, e>>1, m))%m;
  }
}

Très rapide (et pas plus lent que le pire cas : 1302)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete