Re: TV Zap

Le 15/10/2023 à 09:43, pehache a écrit :

C'est comme une multiplication de matrice n*n : une fois n fixé c'est en O(1) :)

Au *second degré* oui (en un sens (*)), mais ici on est au premier:
Si on pose:
Fav(.,c) = a*c + b [mod N]
on entre dans les générateurs aléatoires congruentiels *linéaires*.
___
(*) Linéaires, pas quadratiques :)
Et alors
         Far(.,c) = Fav^(N-1)
                  = (b*(a^(N-1)-1)/(a-1) + c*a^(N-1) [mod n]
                  = b*(a^(N-2)+...+a²+a+1) + c*a^(N-2) [mod N]
                  = A*c + B [mod N]
avec
                A = a^(n-1) [mod N]
et             B = a^(N-2)+...+a²+a+1) + c*a^(N-2) [mod N]
qui peuvent tous deux être précalculés et sont de taille comparable aux a et b de départ, donnant alors un temps de calcul de Far() strictement identique à celui de Fav().
Comme déjà dit: une composition d'opérations linéaires en arithmétique modulaire est une autre opération linéaire modulaire. Ca ne change pas de complexité.
Avec ces générateurs et des a et b bien choisis, on a un mélange bien meilleur qu'une simple addition modulaire. Ta solution avec S=7 correspond à a=0, b=7 qui est un mélange plus faible.
sam.