Kyopro Library
読み取り中…
検索中…
一致する文字列を見つけられません
modcal.hpp
[詳解]
1
#
pragma
once
2
#
include
"../../kyopro_library/template.hpp"
3
4
/// @brief x^n (mod m) を返す
5
template
<
typename
T=ll>
6
T
ModPow
(T x, T n, T mod) {
7
T ret=1;
8
if
(
typeid
(T)==
typeid
(ll)&&mod>INF*2)
return
ModPow<lll>(x,n,mod);
9
while
(n>0) {
10
if
(n&1) (ret*=x)%=mod;
11
(x*=x)%=mod;
12
n>>=1;
13
}
14
return
ret;
15
}
16
17
/// @brief x^(-1) (mod m) を返す
18
ll
ModInv
(ll a, ll m) {
19
ll b=m,u=1,v=0;
20
while
(b) {
21
ll t=a/b;
22
a-=t*b; swap(a,b);
23
u-=t*v; swap(u,v);
24
}
25
return
(u+m)%m;
26
}
ModPow
T ModPow(T x, T n, T mod)
x^n (mod m) を返す
Definition
modcal.hpp:6
ModInv
ll ModInv(ll a, ll m)
x^(-1) (mod m) を返す
Definition
modcal.hpp:18
others
modcal.hpp
構築:
1.13.2