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

needed help in modular arithmatic.
Автор hars123, история, 7 лет назад, По-английски

I am recently solving a problem to find a^(n!)%m and got stuck. please suggest how to solve this problem and some resources and problems to learn concepts related to modular arithmatic.

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

What are the constraints for a, n, and m?

If a and n are small, and gcd(a, m) = 1 (a & m are coprime)

Then first, remember that where φ(m) is the euler totient function of m. That means, we can simplify to

You can calculate φ(m) in O(sqrt(m)) and then calculate in O(n) and then the power with binary exponentiation in O(log2(m)) so the total complexity is O(sqrt(m) + n + log2(m))

→ Ответить