cpp/math/binary-power-method.cpp

• View this file on GitHub
• Last update: 2024-01-29 17:54:25+09:00

Required by

• cpp/data-structure/big-int.cpp
• cpp/geometry/two-points-distance.cpp
• cpp/math/convolution.cpp
• cpp/math/miller-rabin.cpp
• cpp/math/rho.cpp

Verified with

• cpp/z_test/aoj-NTL_2_F.test.cpp
• cpp/z_test/yosupo-addition_of_big_integers.test.cpp
• cpp/z_test/yosupo-convolution_mod.cpp
• cpp/z_test/yosupo-factorize.test.cpp
• cpp/z_test/yosupo-primality_test.test.cpp

Code

#pragma once

template <typename T>
T uPow(T z,T n, T mod){
  T ans = 1;
  while(n != 0){
    if(n%2){
      ans*=z;
      if(mod)ans%=mod;
    }
    n >>= 1;
    z*=z;
    if(mod)z%=mod;
  }
  return ans;
}

#line 2 "cpp/math/binary-power-method.cpp"

template <typename T>
T uPow(T z,T n, T mod){
  T ans = 1;
  while(n != 0){
    if(n%2){
      ans*=z;
      if(mod)ans%=mod;
    }
    n >>= 1;
    z*=z;
    if(mod)z%=mod;
  }
  return ans;
}

Back to top page