Calcul modulo grand nombre [Résolu]

La technique (je pense) la plus simple si tu veux pouvoir gérer des nombres énormes, c'est de les saisir en tant que chaine de caractères, que tu fractionnes ensuite dans plusieurs int (ils sont gentils les int :)) après t'as juste à faire une petite fonction qui te prendre ce tableau (unicolonne) de int et t'en fais ce que tu veux ^^.

Pour le cas du modulo, tu sais que (a×b+c)%m = ( (a%m)×(b%m)+c%m ) % m
Ici le b serait une simple puissance de 10 correspondant à la situation de la coupure.

Pour reprendre ton exemple :
x_initial = 123456789012345
m = 97
Par exemple en coupant de cette manière :
x[0]=1234567
x[1]=89012345
on a donc x_initial = x[0] × 10^8 + x[1]

tu fais donc :
1234567 % 97 = 48
(10^8) % 97 = 81 (obtenu avec une simple boucle for autant de fois que la puissance de 10, en multipliant par 10 à chaque fois et en prenant le modulo : 10%97=10 ; 100%97=3 ; 30%97=30 ; 300%97=9 ; 90%97=90 ; 900%97=27 ; 270%97=76 ; 760%97=81)
89012345 % 97 = 4

ce qui te donne (48*81+4)%97=12

Tu peux bien évidemment fractionner ton nombre de + de morceau la formule est bien sûr toujours valable, ça te ferait juste de simples additions supplémentaires. Tu peux ainsi trouver le modulo 97 d'un nombre de 8000 chiffres si tu veux de la même manière (en ayant fractionné ton nombre en 1000 int de 8 chiffres chacun)

Effectivement :

#include <stdio.h>

int main(){
    long long int x = 123456789012345;
    printf("%lld\n",x % 97);
    return 0;
}

... me donne :

(mando@aldur) (~) $ gcc -W -Wall plop.c
plop.c: In function ‘main’:
plop.c:4: warning: integer constant is too large for ‘long’ type

Ceci dit malgré le warning, le programme donne bien 12... Quand j'ai vu le warning je n'ai même pas pris le temps de tester :p

Normal. T'as obligé LL à la fin de l'initialisation.
Teste :

long long int x = 123456789012345LL;

Ca devrait enlever le warning ;)

Tout dépend de ce que tu utilises. Par exemple sous linux avec bc ça se fait sans problème :

(mando@aldur) (~) $ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
123456789012345%97
12

Par contre c'est vrai qu'en C par exemple, même avec des long long int ça ne marche pas...

bravo a tous et merci !

petit ajout le 'LL' est obligatoire après l'initialisation du grand nombre en C++ car il n'y a pas de warning mais une erreur a la compilation ;) encore merci