Forum dédié aux énigmes et à toutes formes de jeux de logique. | Déconnexion |
|
Tu n'es pas identifié sur Prise2tete : s'identifier.  Accueil
Forum
|
 |
Écrire une réponseRésumé de la discussion
Merci scarta pour ces explications qui sont très claires.
La méthode par unité tronquée marche, oui.
J'ai corrigé mon message #10.
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.
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) )
La magie du O(ln)
Résultat=10, en 0,02 seconde aussi
Tu peux regarder pour 1302? C'est le pire cas normalement
@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
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) |
 |
| Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact | ||
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.
