Как преобразовать двойное значение в PQ ^ -1 по модулю MOD напрямую, где q взаимно просто с MOD

Question

Я имею дело с вопросом о вероятности, где вероятность может быть выражена в виде дроби P / Q, где P и Q являются целыми числами (P≥0, Q> 0), а Q является взаимно простым с 998 244 353. Вы должны вычислить P⋅Q ^ −1 по модулю 998,244,353.

Answer 1

Вы не можете. Значения с плавающей точкой не являются точными, так что это все равно, что пытаться преобразовать десятичную дробь в дробную после ее округления. Вам необходимо выполнить мод расчетов 998244353, начиная с начала, и вместо того, чтобы делить вас, умножьте на модульное обратное. Можно доказать, что выполнение этого равносильно выполнению всех вычислений с использованием точных дробей и преобразованию в модульную форму в самом конце.

Answer 2

Вы можете использовать Маленькая теорема Ферма

, это может быть полезно, если вы ищете код

Answer 3

Это можно решить с помощью Расширенного евклидова алгоритма . Вы можете посетить следующую ссылку для получения дополнительной информации и решения кода:

https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/