Задача 288
Громадный факториал

Для любого простого числа p можно определить число N(p,q) = _(n=0 до q) T_(n)*p^(n),
где T_(n) получают с помощью следующего генератора случайных чисел:

S_(0) = 290797
S_(n+1) = S_(n)^(2) mod 50515093
T_(n) = S_(n) mod p

Пусть Nfac(p,q) является факториалом N(p,q).
Пусть NF(p,q) является числом множителей p в Nfac(p,q).

Дано, что NF(3,10000) mod 3^(20)=624955285.

Найдите NF(61,10^(7)) mod 61^(10).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net