src/math/pow_mod_ll.hpp

• View this file on GitHub
• Last update: 2025-11-13 05:48:47+08:00
• Include: #include "src/math/pow_mod_ll.hpp"

Required by

• src/math/millerrabin.hpp
• src/math/pollardrho.hpp
• src/math/proot.hpp

Verified with

• test/math/millerrabin.test.cpp
• test/math/pollardrho.test.cpp
• test/math/proot.test.cpp

Code

ll pow_mod_ll(ll a, ull n, ll p) {
  ll ret = 1;
  for (; n; n /= 2) {
    if (n & 1) ret = i128(ret) * a % p;
    a = i128(a) * a % p;
  }
  return ret;
}

#line 1 "src/math/pow_mod_ll.hpp"
ll pow_mod_ll(ll a, ull n, ll p) {
  ll ret = 1;
  for (; n; n /= 2) {
    if (n & 1) ret = i128(ret) * a % p;
    a = i128(a) * a % p;
  }
  return ret;
}

Back to top page