(x^y)%mod
(math/mod_pow.hpp)
- View this file on GitHub
- Last update: 2020-09-13 16:40:58+09:00
- Include:
#include "math/mod_pow.hpp"
Required by
形式的冪級数(Integer)
(math/FPS_long.hpp)
- 形式的冪級数(ModInt)
(math/FPS_mint.hpp)
- ガーナーのアルゴリズム
(math/garner.hpp)
- math/kth_root.hpp
- 離散対数(ModLog)
(math/mod_log.hpp)
- ModSqrt
(math/mod_sqrt.hpp)
- テトレーション
(math/tetration.hpp)
Verified with
- graph_tree/test/LC_centroid_decomposition.test.cpp
- math/test/LC_convolution_1000000007.test.cpp
- math/test/LC_convolution_998244353.test.cpp
- math/test/LC_interpolation.test.cpp
- math/test/LC_mod_log.test.cpp
- math/test/LC_mod_sqrt.test.cpp
- math/test/LC_tetration.test.cpp
Code
/**
* @brief (x^y)%mod
*/
long long mod_pow(long long x,long long y,long long mod){
long long ret=1;
while(y>0) {
if(y&1)(ret*=x)%=mod;
(x*=x)%=mod;
y>>=1;
}
return ret;
}#line 1 "math/mod_pow.hpp"
/**
* @brief (x^y)%mod
*/
long long mod_pow(long long x,long long y,long long mod){
long long ret=1;
while(y>0) {
if(y&1)(ret*=x)%=mod;
(x*=x)%=mod;
y>>=1;
}
return ret;
}