As you know, in [this](https://codeforces.net/blog/entry/126654) reason, 64-bit C++ compilers are temporarily disabled.↵
↵
In order to keep using __int128 (at least partially) in 32-bit compilers, I'm trying writing a template of the **unsigned** version of __int128.↵
↵
On 2024/3/15, I completed writing the alpha version of it.↵
↵
If you find bugs in my code, please leave a comment below. Thanks!↵
↵
**UPD**:↵
↵
2024/3/14: added (maybe) all operators that an __int128 has except for `operator/` / fixed infinite-recursion bug in several operators↵
↵
2024/3/15: added `operator/` / fixed many bugs in almost all arithmetic operators / completed first (buggy) version of this handmade __int128↵
↵
Here's it (not completed yet):↵
↵
<spoiler summary="integer_128_impl.cpp">↵
↵
~~~~~↵
#include<tuple>↵
#include<iostream>↵
#include<climits>↵
↵
namespace RedshiftShine{↵
↵
using ll=unsigned long long;↵
const ll ulmx=ULLONG_MAX;↵
const ll shift=64;↵
↵
ll min(ll x,ll y){↵
return x<y?x:y;↵
}↵
↵
ll max(ll x,ll y){↵
return x>y?x:y;↵
}↵
↵
bool detect_overflow_add(ll x,ll y){↵
return x+y<min(x,y);↵
}↵
↵
bool detect_overflow_minus(ll x,ll y){↵
return x<y;↵
}↵
↵
class Custom_Unsigned_int128{↵
private:↵
ll higherInt,lowerInt;↵
public:↵
Custom_Unsigned_int128(){}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128(_Tp x):↵
higherInt(0),↵
lowerInt(x){}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128(_Tp x,_Tp y):↵
higherInt(x),↵
lowerInt(y){}↵
↵
Custom_Unsigned_int128↵
(const Custom_Unsigned_int128& ele):↵
higherInt(ele.higherInt),↵
lowerInt(ele.lowerInt){}↵
↵
std::pair<ll,ll>↵
base_access(){↵
return std::pair<ll,ll>{↵
higherInt,↵
lowerInt↵
};↵
}↵
↵
Custom_Unsigned_int128&↵
operator=(const Custom_Unsigned_int128& x){↵
higherInt=x.higherInt,↵
lowerInt=x.lowerInt;↵
return *this;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator=(const _Tp& x){↵
*this=Custom_Unsigned_int128↵
(↵
0,x↵
);↵
return *this;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator+(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt+↵
detect_overflow_add(lowerInt,x),↵
lowerInt+x↵
);↵
}↵
↵
template<typename _Tp>↵
friend Custom_Unsigned_int128↵
operator+(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt+↵
detect_overflow_add(ele.lowerInt,x),↵
ele.lowerInt+x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator+(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt+x.higherInt+↵
detect_overflow_add(lowerInt,x.lowerInt),↵
lowerInt+x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator==(const _Tp& x)const{↵
return ↵
(↵
!higherInt and ↵
lowerInt==x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator==(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ele==x;↵
}↵
↵
bool↵
operator==(const Custom_Unsigned_int128& x)const{↵
return ↵
(↵
higherInt==x.higherInt and ↵
lowerInt==x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator!=(const _Tp& x)const{↵
return !(*this==x);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator!=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele==x);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator<(const _Tp& x)const{↵
return ↵
(↵
!higherInt and ↵
lowerInt<x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator<(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ↵
(↵
ele.higherInt or ↵
ele.lowerInt>x↵
);↵
}↵
↵
bool↵
operator<(const Custom_Unsigned_int128& x)const{↵
↵
return ↵
(↵
higherInt<x.higherInt or ↵
(↵
higherInt==x.higherInt and ↵
lowerInt<x.lowerInt↵
)↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator<=(const _Tp& x)const{↵
return ↵
(↵
*this<x or ↵
*this==x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator<=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ele<=x;↵
}↵
↵
bool↵
operator<=(const Custom_Unsigned_int128& x)const{↵
return ↵
(↵
*this<x or ↵
*this==x↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator>(const _Tp& x)const{↵
return ↵
!(↵
*this<=x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator>(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele<=x);↵
}↵
↵
bool↵
operator>(const Custom_Unsigned_int128& x)const{↵
return ↵
!(↵
*this<=x↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator>=(const _Tp& x)const{↵
return ↵
!(↵
*this<x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator>=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele<x);↵
}↵
↵
bool↵
operator>=(const Custom_Unsigned_int128& x)const{↵
return ↵
!(↵
*this<x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator+=(const _Tp& x){↵
return *this=*this+x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator-(const _Tp& x)const{↵
return Custom_Unsigned_int128↵
(↵
higherInt-↵
detect_overflow_minus(lowerInt,x),↵
lowerInt-x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator-(const Custom_Unsigned_int128& x)const{↵
return Custom_Unsigned_int128↵
(↵
higherInt-x.higherInt-↵
detect_overflow_minus(lowerInt,x.lowerInt),↵
lowerInt-x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator-=(const _Tp& x){↵
return *this=*this-x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator&(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
0ull,↵
lowerInt&x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator&(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt&x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator&(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt&x.higherInt,↵
lowerInt&x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator&=(const _Tp& x){↵
return *this=*this&x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator|(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt,↵
lowerInt|x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator|(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt|x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator|(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt|x.higherInt,↵
lowerInt|x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator|=(const _Tp& x){↵
return *this=*this|x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator^(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt,↵
lowerInt^x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator^(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt^x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator^(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt^x.higherInt,↵
lowerInt^x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator^=(const _Tp& x){↵
return *this=*this^x;↵
}↵
↵
Custom_Unsigned_int128↵
operator~(){↵
return Custom_Unsigned_int128(↵
~higherInt,↵
~lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator<<(const _Tp& x){↵
return x<shift?↵
Custom_Unsigned_int128(↵
higherInt<<x|(lowerInt>>(shift-x)),↵
lowerInt<<x↵
):↵
Custom_Unsigned_int128(↵
lowerInt<<(x-shift),↵
0ull↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator<<=(const _Tp& x){↵
return *this=*this<<x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator>>(const _Tp& x){↵
return x<shift?↵
Custom_Unsigned_int128(↵
higherInt>>x,↵
lowerInt>>x|(higherInt<<(shift-x))↵
):↵
Custom_Unsigned_int128(↵
0ull,↵
higherInt>>(x-shift)↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator>>=(const _Tp& x){↵
return *this=*this>>x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator*(const _Tp& x)const{↵
Custom_Unsigned_int128 ret(0),pr(*this);↵
_Tp tm(x);↵
for(;tm;tm>>=1){↵
if(tm&1)ret+=pr;↵
pr<<=1;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){↵
Custom_Unsigned_int128 ret(0),pr(ele);↵
_Tp tm(x);↵
for(;tm!=0;tm>>=1){↵
if((tm&1)!=0)ret+=pr;↵
pr+=pr;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator*=(const _Tp& x){↵
return *this=*this*x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator/(const _Tp& x)const{↵
Custom_Unsigned_int128 ret(0),pr(x),trm(1),ts(*this);↵
while((!(pr.higherInt>>(shift-1))) and pr<=ts){↵
↵
pr<<=1,trm<<=1;↵
↵
}↵
pr>>=1,trm>>=1;↵
for(;;pr>>=1,trm>>=1){↵
↵
// if(ts<pr)continue;↵
↵
while(ts>=pr){↵
ts-=pr,ret+=trm;↵
↵
}↵
if((pr&1)!=0)break;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator/=(const _Tp& x){↵
return *this=*this/x;↵
}↵
↵
template<typename _Tp>↵
_Tp↵
operator%(const _Tp& x)const{↵
return (*this-*this/x*x).lowerInt;↵
}↵
↵
Custom_Unsigned_int128↵
operator%(const Custom_Unsigned_int128& x)const{↵
return *this-*this/x*x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator%=(const _Tp& x){↵
return *this=*this%x;↵
}↵
↵
};↵
↵
}↵
↵
void print(RedshiftShine::Custom_Unsigned_int128 v){↵
if(v==0)return;↵
print(v/10);↵
putchar(v%10+'0');↵
}↵
↵
void test(){↵
RedshiftShine::Custom_Unsigned_int128 ci(0,1),cz(0,1);↵
print(ci),putchar(' ');↵
for(int i=128;i;i--){↵
std::swap(ci,cz);↵
cz+=ci;↵
print(cz),putchar(' ');↵
}↵
}↵
↵
int main(){↵
test();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
In order to keep using __int128 (at least partially) in 32-bit compilers, I'm trying writing a template of the **unsigned** version of __int128.↵
↵
On 2024/3/15, I completed writing the alpha version of it.↵
↵
If you find bugs in my code, please leave a comment below. Thanks!↵
↵
**UPD**:↵
↵
2024/3/14: added (maybe) all operators that an __int128 has except for `operator/` / fixed infinite-recursion bug in several operators↵
↵
2024/3/15: added `operator/` / fixed many bugs in almost all arithmetic operators / completed first (buggy) version of this handmade __int128↵
↵
Here's it
↵
<spoiler summary="integer_128_impl.cpp">↵
↵
~~~~~↵
#include<tuple>↵
#include<iostream>↵
#include<climits>↵
↵
namespace RedshiftShine{↵
↵
using ll=unsigned long long;↵
const ll ulmx=ULLONG_MAX;↵
const ll shift=64;↵
↵
ll min(ll x,ll y){↵
return x<y?x:y;↵
}↵
↵
ll max(ll x,ll y){↵
return x>y?x:y;↵
}↵
↵
bool detect_overflow_add(ll x,ll y){↵
return x+y<min(x,y);↵
}↵
↵
bool detect_overflow_minus(ll x,ll y){↵
return x<y;↵
}↵
↵
class Custom_Unsigned_int128{↵
private:↵
ll higherInt,lowerInt;↵
public:↵
Custom_Unsigned_int128(){}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128(_Tp x):↵
higherInt(0),↵
lowerInt(x){}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128(_Tp x,_Tp y):↵
higherInt(x),↵
lowerInt(y){}↵
↵
Custom_Unsigned_int128↵
(const Custom_Unsigned_int128& ele):↵
higherInt(ele.higherInt),↵
lowerInt(ele.lowerInt){}↵
↵
std::pair<ll,ll>↵
base_access(){↵
return std::pair<ll,ll>{↵
higherInt,↵
lowerInt↵
};↵
}↵
↵
Custom_Unsigned_int128&↵
operator=(const Custom_Unsigned_int128& x){↵
higherInt=x.higherInt,↵
lowerInt=x.lowerInt;↵
return *this;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator=(const _Tp& x){↵
*this=Custom_Unsigned_int128↵
(↵
0,x↵
);↵
return *this;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator+(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt+↵
detect_overflow_add(lowerInt,x),↵
lowerInt+x↵
);↵
}↵
↵
template<typename _Tp>↵
friend Custom_Unsigned_int128↵
operator+(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt+↵
detect_overflow_add(ele.lowerInt,x),↵
ele.lowerInt+x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator+(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt+x.higherInt+↵
detect_overflow_add(lowerInt,x.lowerInt),↵
lowerInt+x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator==(const _Tp& x)const{↵
return ↵
(↵
!higherInt and ↵
lowerInt==x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator==(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ele==x;↵
}↵
↵
bool↵
operator==(const Custom_Unsigned_int128& x)const{↵
return ↵
(↵
higherInt==x.higherInt and ↵
lowerInt==x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator!=(const _Tp& x)const{↵
return !(*this==x);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator!=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele==x);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator<(const _Tp& x)const{↵
return ↵
(↵
!higherInt and ↵
lowerInt<x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator<(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ↵
(↵
ele.higherInt or ↵
ele.lowerInt>x↵
);↵
}↵
↵
bool↵
operator<(const Custom_Unsigned_int128& x)const{↵
↵
return ↵
(↵
higherInt<x.higherInt or ↵
(↵
higherInt==x.higherInt and ↵
lowerInt<x.lowerInt↵
)↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator<=(const _Tp& x)const{↵
return ↵
(↵
*this<x or ↵
*this==x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator<=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return ele<=x;↵
}↵
↵
bool↵
operator<=(const Custom_Unsigned_int128& x)const{↵
return ↵
(↵
*this<x or ↵
*this==x↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator>(const _Tp& x)const{↵
return ↵
!(↵
*this<=x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator>(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele<=x);↵
}↵
↵
bool↵
operator>(const Custom_Unsigned_int128& x)const{↵
return ↵
!(↵
*this<=x↵
);↵
}↵
↵
template<typename _Tp>↵
bool↵
operator>=(const _Tp& x)const{↵
return ↵
!(↵
*this<x↵
);↵
}↵
↵
template<typename _Tp>↵
friend bool↵
operator>=(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return !(ele<x);↵
}↵
↵
bool↵
operator>=(const Custom_Unsigned_int128& x)const{↵
return ↵
!(↵
*this<x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator+=(const _Tp& x){↵
return *this=*this+x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator-(const _Tp& x)const{↵
return Custom_Unsigned_int128↵
(↵
higherInt-↵
detect_overflow_minus(lowerInt,x),↵
lowerInt-x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator-(const Custom_Unsigned_int128& x)const{↵
return Custom_Unsigned_int128↵
(↵
higherInt-x.higherInt-↵
detect_overflow_minus(lowerInt,x.lowerInt),↵
lowerInt-x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator-=(const _Tp& x){↵
return *this=*this-x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator&(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
0ull,↵
lowerInt&x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator&(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt&x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator&(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt&x.higherInt,↵
lowerInt&x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator&=(const _Tp& x){↵
return *this=*this&x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator|(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt,↵
lowerInt|x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator|(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt|x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator|(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt|x.higherInt,↵
lowerInt|x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator|=(const _Tp& x){↵
return *this=*this|x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator^(const _Tp& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt,↵
lowerInt^x↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator^(const _Tp& x,const Custom_Unsigned_int128& ele){↵
return Custom_Unsigned_int128↵
(↵
ele.higherInt,↵
ele.lowerInt^x↵
);↵
}↵
↵
Custom_Unsigned_int128↵
operator^(const Custom_Unsigned_int128& x){↵
return Custom_Unsigned_int128↵
(↵
higherInt^x.higherInt,↵
lowerInt^x.lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator^=(const _Tp& x){↵
return *this=*this^x;↵
}↵
↵
Custom_Unsigned_int128↵
operator~(){↵
return Custom_Unsigned_int128(↵
~higherInt,↵
~lowerInt↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator<<(const _Tp& x){↵
return x<shift?↵
Custom_Unsigned_int128(↵
higherInt<<x|(lowerInt>>(shift-x)),↵
lowerInt<<x↵
):↵
Custom_Unsigned_int128(↵
lowerInt<<(x-shift),↵
0ull↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator<<=(const _Tp& x){↵
return *this=*this<<x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator>>(const _Tp& x){↵
return x<shift?↵
Custom_Unsigned_int128(↵
higherInt>>x,↵
lowerInt>>x|(higherInt<<(shift-x))↵
):↵
Custom_Unsigned_int128(↵
0ull,↵
higherInt>>(x-shift)↵
);↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator>>=(const _Tp& x){↵
return *this=*this>>x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator*(const _Tp& x)const{↵
Custom_Unsigned_int128 ret(0),pr(*this);↵
_Tp tm(x);↵
for(;tm;tm>>=1){↵
if(tm&1)ret+=pr;↵
pr<<=1;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){↵
Custom_Unsigned_int128 ret(0),pr(ele);↵
_Tp tm(x);↵
for(;tm!=0;tm>>=1){↵
if((tm&1)!=0)ret+=pr;↵
pr+=pr;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator*=(const _Tp& x){↵
return *this=*this*x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128↵
operator/(const _Tp& x)const{↵
Custom_Unsigned_int128 ret(0),pr(x),trm(1),ts(*this);↵
while((!(pr.higherInt>>(shift-1))) and pr<=ts){↵
↵
pr<<=1,trm<<=1;↵
↵
}↵
pr>>=1,trm>>=1;↵
for(;;pr>>=1,trm>>=1){↵
↵
// if(ts<pr)continue;↵
↵
while(ts>=pr){↵
ts-=pr,ret+=trm;↵
↵
}↵
if((pr&1)!=0)break;↵
}↵
return ret;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator/=(const _Tp& x){↵
return *this=*this/x;↵
}↵
↵
template<typename _Tp>↵
_Tp↵
operator%(const _Tp& x)const{↵
return (*this-*this/x*x).lowerInt;↵
}↵
↵
Custom_Unsigned_int128↵
operator%(const Custom_Unsigned_int128& x)const{↵
return *this-*this/x*x;↵
}↵
↵
template<typename _Tp>↵
Custom_Unsigned_int128&↵
operator%=(const _Tp& x){↵
return *this=*this%x;↵
}↵
↵
};↵
↵
}↵
↵
void print(RedshiftShine::Custom_Unsigned_int128 v){↵
if(v==0)return;↵
print(v/10);↵
putchar(v%10+'0');↵
}↵
↵
void test(){↵
RedshiftShine::Custom_Unsigned_int128 ci(0,1),cz(0,1);↵
print(ci),putchar(' ');↵
for(int i=128;i;i--){↵
std::swap(ci,cz);↵
cz+=ci;↵
print(cz),putchar(' ');↵
}↵
}↵
↵
int main(){↵
test();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
