Подобный вывод используется, чтобы было понятно, что вы способны, если нужно, вычислить с точностью до обыкновенной дроби, но в длинную арифметику (а дроби бывают длинные) не лезть. Ибо реализации длинной арифметики различаются по эффективности от ЯП к ЯП, а в некоторых вообще нет штатной (внешние библиотеки в олимпиадном программировании запрещены).
Числа P и Q высчитываем с точностью до остатка от деления на Z := 109+ 7.
Авторы обещают, что Q mod Z ≠ 0. Z — простое. Тогда НОД(Q mod Z, Z) = 1. Так называемый расширенный алгоритм Евклида (гуглите!) позволяет подобрать такие числа, чтобы m(Q mod Z) + nZ = 1.
Ваша задача — вывести ((P mod Z) · m) mod Z. Специально указал дважды mod Z: первое у вас будет при работе с числом P, второе — при генерации вывода.
Почему так? Возьмём вместо здоровенного Z цифру поменьше, 17. Если у вас получился результат 100/400, при расчётах выйдет цифра 15/9, и 9·2+17·(−1) = 1, и ваша задача — вывести (15·2) mod 17 = 13.
Если же у вас получилось, например, 35/140, при расчётах получается 1/4, 1·(−4)+17·1 = 1, и вы должны вывести (1·(−4)) mod 17 = 13. То есть: независимо от того, насколько сократимая дробь у вас получилась, вы получите один и тот же результат. Тут надо уточнить: там, где возможен отрицательный числитель, нужен не обычный % из Си++, а (a % Z; если получилось отрицательное — добавь Z).
Ну а арифметических переполнений просто не допускайте, Z = 109 + 7 позволяет умножать в типе long long и не уходить в переполнение.
UPD. То, что Z — простое, даёт несколько выгод. Часто результат бывает круглый, и простота требует честно считать остаток, а не угадывать. Ну и побочек меньше.
