math/modpow.hpp

• View this file on GitHub
• Last update: 2023-03-13 22:17:07+09:00
• Include: #include "math/modpow.hpp"

Verified with

• test/aoj/NTL/NTL_1_B.test.cpp

Code

ll modPow(ll a, ll n, ll p){
  a %= p;
  ll res = 1;
  while(n){
    if(n & 1) (res *= a) %= p;
    (a *= a) %= p;
    n >>= 1;
  }
  return res;
}

#line 1 "math/modpow.hpp"
ll modPow(ll a, ll n, ll p){
  a %= p;
  ll res = 1;
  while(n){
    if(n & 1) (res *= a) %= p;
    (a *= a) %= p;
    n >>= 1;
  }
  return res;
}

Back to top page