拡張ユークリッドの互除法
code:cpp
template< typename T >
T extgcd(T a, T b, T &x, T &y) {
T d = a;
if(b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
} else {
x = 1;
y = 0;
}
return d;
}
long long llceil(long long a,long long b){
if(a%b==0){return a/b;}
if(a>=0){return (a/b)+1;}
else{return -((-a)/b);}
}
long long llfloor(long long a,long long b){
if(a%b==0){return a/b;}
if(a>=0){return (a/b);}
else{return -((-a)/b)-1;}
}