très grand nombre modulo nombre premier

Question

On m'a posé la question suivante dans une interview:

Comment résoudre ceci: (!! (3000000)/(30)^100000)% (tout premier pas.)

J'ai codé le programme C pour celui-ci en utilisant la force brute, mais je suis sûr qu'il ne s'attendait pas à cela. Des suggestions pour les solutions?

Answer 1

3000000! = 1*2*3*4*5*..*8*...*16*...*24*...*32*...40*...*64*...*3000000

Peut-on compter le nombre de s dans le résultat? Oui, chaque puissance de contribue un à chacun de ses multiples. Donc, le nombre total de s dans la factorisation de n! est n/2 + n/4 + n/8 + n/16 + n/32 + ... où / est une division entière et les conditions se résument alors qu'ils sont supérieurs à 0:

fnf n f = -- number of `f` factors in `n!` 
    sum . takeWhile (>0) . tail . iterate (`div` f) $ n 

(écrire le pseudocode in Haskell). quand f*f < n, il y aura plus d'une entrée à résumer. Pour plus de f s, il n'y aura qu'une seule entrée à additionner, à savoir. n `div` f.

Ainsi, la factorisation de n! se trouve que

factfact n = -- factorization of n! as [ (p,k) ... ] for n! = PROD p_i^k_i 
    let 
    (ps,qs) = span (\p-> p*p <= n) primes -- (before, after) 
    in 
    [(f, fnf n f) | f <- ps] ++ 
    [(f, n `div` f) | f <- takeWhile (<= n) qs] 

Maintenant, factorisation de ! a 10 facteurs:

> factfact 30 
[(2,26),(3,14),(5,7),(7,4),(11,2),(13,2),(17,1),(19,1),(23,1),(29,1)] 

Le ième puissance de celui-ci vient de chacun de ses coefficients de facteur multiplié par . ! Quand nous prenons la factorisation de , ses premiers termes sur 216816 au total, sont les suivants:

> factfact 3000000 
[(2,2999990),(3,1499993),(5,749998),(7,499996),(11,299996),(13,249998), 
(17,187497),(19,166665),(23,136361),(29,107142),(31,99998), ... 

donc après la division lorsque nous soustrayons la deuxième de la première ne manquent ni annulé complètement:

[(2,399990),(3,99993),(5,49998),(7,99996),(11,99996),(13,49998), 
(17,87497),(19,66665),(23,36361),(29,7142),(31,99998), ... 

Donc, pour tout premier inférieur à 3000000 le reste est 0. Et s'il est plus grand, p > 3000000? Ensuite, exponentiation modulaire mod p et multiplication mod p pour cette factorisation, que nous avons trouvé ci-dessus, doit être utilisé. Il y a beaucoup de réponses à propos de ça, sur SO. Bien sûr, dans le code de production (pour un langage de programmation non fainéant), nous ne construirions pas la liste de factorisation intermédiaire, mais traiterions chaque prime en dessous de 3000000, un par un (pas besoin d'un paresseux la langue).