Блог пользователя vignesh_in_zone

Автор vignesh_in_zone, история, 4 года назад, По-английски

given three numbers p , q, r calculate the pow( p , q!) % r

It would also be helpful if you could mention the important concepts needed in solving this problem ,

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

If $$$p$$$ and $$$r$$$ are relatively prime you use Euler's theorem $$$p^{\phi(r)} = 1$$$ mod $$$r$$$. So you need to calculate $$$q!$$$ mod $$$\phi(r)$$$. $$$\phi$$$ is the Euler totient function, for a prime $$$r$$$ it is just $$$r-1$$$. You can find the answer even if $$$(p, r) > 1$$$, but it involves additional steps.