Расчет обратного мода, где мод не прост

Question

Я хочу рассчитать стоимость

F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M для заданных значений N,R и M,

Здесь A^B показывает мощность B, а НЕ битовую операцию

Здесь M не обязательно должно быть простым. Как подойти к этому вопросу? Пожалуйста, помогите, потому что, если бы M было простым, что не было бы так трудно найти обратное к R ^ R mod M.

Но так как M может быть любым значением в диапазоне от 1 до 10^9. Я не могу решить эту проблему.

N может составлять от 1 до 10^5, а R меньше или равно N.

Answer 1

Предполагая, что вы как-то знаете, что результатом деления является целое число:

Поскольку N и R малы, вы можете сделать это, вычислив простую факторизацию N-R+1 и R.

Если мы знаем, что R=p^a...q^b затем R^R = p^(Ra)...q^(Rb),

Точно так же вы можете отработать силу каждого простого в (N-R+1)^(N-R+1),

Вычесть силы простых чисел в R^R от сил простых чисел в (N-R+1)^(N-R+1) дает вам силы каждого простого в результате.

Затем вы можете использовать стандартную подпрограмму возведения в степень для вычисления результата по модулю M без инверсий.