Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
modcal.hpp
[詳解]
1#pragma once
2#include"../../kyopro_library/template.hpp"
3
4/// @brief x^n (mod m) を返す
5template<typename T=ll>
6T 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) を返す
18ll 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}
T ModPow(T x, T n, T mod)
x^n (mod m) を返す
Definition modcal.hpp:6
ll ModInv(ll a, ll m)
x^(-1) (mod m) を返す
Definition modcal.hpp:18