__intinf
_nothingGG · · 个人记录
#include<bits/stdc++.h>
namespace std{
class ZeroDivisionError:public exception{public:
const char*what()const throw(){return "__intinf::divmod";}};
class FFTLimitExceededError:public exception{public:
const char*what()const throw(){return "__intinf::fft_mul";}};
class __intinf{
protected:
using digit_t=long long;
static constexpr int WIDTH=8;
static constexpr digit_t BASE=1e8;
static constexpr long long FFT_LIMIT=32;
static constexpr long long NEWTON_LIMIT=128;
static constexpr long long NEWTON_MIN_LEVEL=16;
digit_t* digits;
int capacity,size;
bool flag;
inline void push(const digit_t&);
inline void pop();
inline int compare(const __intinf&) const;
static inline __intinf fft_mul(const __intinf&,const __intinf&);
__intinf newton_inv(int)const;
inline pair<__intinf,__intinf>newton_div(const __intinf&)const;
template<class F>inline static __intinf binary_op_helper(const __intinf&,const __intinf&,const F&);
protected:
inline void resize(const int&);
public:
inline void reserve(const int&);
__intinf():digits(nullptr),flag(true){*this=0;}
__intinf(const __intinf&x):digits(nullptr){*this=x;}
__intinf(const long long&x):digits(nullptr){*this=x;}
__intinf(const string&s):digits(nullptr){*this=s;}
__intinf(const vector<bool>&b):digits(nullptr){*this=b;}
template<class BoolIt>__intinf(const BoolIt& begin,const BoolIt& end):digits(nullptr)
{*this=vector<bool>(begin,end);}
__intinf&operator=(const __intinf&);
__intinf&operator=(const long long&);
__intinf&operator=(const string&);
__intinf&operator=(const vector<bool>&);
void clear();
~__intinf(){clear();}
friend ostream&operator<<(ostream&out,const __intinf&x){
if(!x.flag)out<<'-';
out<<(long long)x.digits[x.size];
for(int i=x.size-1;i>=1;i--)
out<<setw(WIDTH)<<setfill('0')<<(long long)x.digits[i];
return out;
}
friend istream&operator>>(istream& in,__intinf& x){
string s;in>>s;x=s;
return in;
}
string to_string()const;
long long to_long_long()const;
vector<bool>to_binary()const;
int _digit_len()const;
__intinf operator-()const;
__intinf operator~()const;
__intinf abs()const;
static __intinf abs(const __intinf&);
bool operator==(const __intinf&)const;
#if __cplusplus >= 202002L
auto operator<=>(const __intinf&)const;
#else
bool operator<(const __intinf&)const;
bool operator>(const __intinf&)const;
bool operator!=(const __intinf&)const;
bool operator<=(const __intinf&)const;
bool operator>=(const __intinf&)const;
#endif
__intinf div2()const;
pair<__intinf,__intinf>divmod(const __intinf&,bool=false)const;
__intinf operator+(const __intinf&)const;
__intinf operator-(const __intinf&)const;
__intinf operator*(const int&)const;
__intinf operator*(const __intinf&)const;
__intinf operator/(const long long&)const;
__intinf operator/(const __intinf&)const;
__intinf operator%(const long long&)const;
__intinf operator%(const __intinf&)const;
__intinf pow(const long long&)const;
__intinf pow(const long long&,const __intinf&)const;
__intinf root(const long long& =2)const;
__intinf sqrt()const;
__intinf gcd(const __intinf&)const;
__intinf lcm(const __intinf&)const;
static __intinf pow(const __intinf&,const long long&);
static __intinf pow(const __intinf&,const long long&,const __intinf&);
static __intinf root(const __intinf&,const long long&);
static __intinf sqrt(const __intinf&);
static __intinf gcd(const __intinf&,const __intinf&);
static __intinf lcm(const __intinf&,const __intinf&);
inline __intinf _move_l(int)const;
inline __intinf _move_r(int)const;
__intinf&operator+=(const __intinf&);
__intinf&operator-=(const __intinf&);
__intinf&operator*=(int);
__intinf&operator*=(const __intinf&);
__intinf&operator/=(const long long&);
__intinf&operator/=(const __intinf&);
__intinf&operator%=(const long long&);
__intinf&operator%=(const __intinf&);
__intinf operator<<(const long long&);
__intinf operator>>(const long long&);
__intinf&operator<<=(const long long&);
__intinf&operator>>=(const long long&);
__intinf operator&(const __intinf&);
__intinf operator|(const __intinf&);
__intinf operator^(const __intinf&);
__intinf&operator&=(const __intinf&);
__intinf&operator|=(const __intinf&);
__intinf&operator^=(const __intinf&);
__intinf&operator++();
__intinf operator++(int);
__intinf&operator--();
__intinf operator--(int);
};
inline void __intinf::push(const digit_t&val){
if(size==capacity){
int new_capacity=0;
if(capacity<256)new_capacity=capacity<<1;
else new_capacity=std::pow(capacity+1,0.125)*capacity;
digit_t* new_digits=new digit_t[new_capacity+1];
memcpy(new_digits,digits,sizeof(long long)*(capacity+1));
delete[] digits;
digits=new_digits,capacity=new_capacity;
}
digits[++size]=val;
}
inline void __intinf::pop(){digits[size--]=0;}
inline int __intinf::compare(const __intinf& x)const{
if(flag&&!x.flag)return 1;
if(!flag&&x.flag)return -1;
int sgn=(flag&&x.flag?1:-1);
if(size>x.size)return sgn;
if(size<x.size)return -sgn;
for(int i=size;i>=1;i--) {
if(digits[i]>x.digits[i])return sgn;
if(digits[i]<x.digits[i])return -sgn;
}
return 0;
}
inline void __intinf::reserve(const int&sz){
if(sz<0)return;
if(digits!=nullptr)delete[] digits;
capacity=sz,size=0;
digits=new digit_t[sz+1];
memset(digits,0,sizeof(digit_t)*(sz+1));
}
inline void __intinf::resize(const int&sz){reserve(sz),size=sz;}
__intinf&__intinf::operator=(const __intinf&x){
reserve(x.size+1);
flag=x.flag,size=x.size;
memcpy(digits,x.digits,sizeof(digit_t)*(x.size+1));
return *this;
}
__intinf&__intinf::operator=(const long long&x){
flag=(x>=0),reserve(4);
if(x==0)return size=1,digits[1]=0,*this;
if(x==LLONG_MIN)return *this="-9223372036854775808";
long long n=std::abs(x);
do{push(n%BASE),n/=BASE;}while(n);
return *this;
}
__intinf&__intinf::operator=(const string&s){
flag=true,reserve(s.size()/WIDTH+1);
if (s.empty()||s=="-")return *this=0;
int i=0;if(s[0]=='-')flag=false,i++;
for(int j=s.size()-1;j>=i;j-=WIDTH){
int start=max(i,j-WIDTH+1),len=j-start+1;
push(stoll(s.substr(start,len)));
}
while(size>1&&digits[size]==0)pop();
return *this;
}
__intinf&__intinf::operator=(const vector<bool>&b){
if(b[0]==0){
*this=0;
__intinf pw2=1;
for(int i=b.size()-1;i>=1;i--,pw2+=pw2)if(b[i])*this+=pw2;
return *this;
}
else{
*this=0;
__intinf pw2=1;
for(int i=b.size()-1;i>=1;i--,pw2+=pw2)if(!b[i])*this-=pw2;
*this-=1;
return *this;
}
}
void __intinf::clear(){if(digits!=nullptr)delete[] digits,digits=nullptr;}
string __intinf::to_string()const{stringstream ss;ss<<*this;return ss.str();}
long long __intinf::to_long_long()const{return stoll(to_string());}
vector<bool>__intinf::to_binary()const{
if(*this==0)return{0};
vector<bool>res;__intinf x;
if(this->flag==true)x=*this;
if(this->flag==false)x=~*this;
for(;x!=0;x=x.div2())
res.emplace_back(this->flag==true?x.digits[1]&1:!(x.digits[1]&1));
if(this->flag==true)res.emplace_back(0);
else res.emplace_back(1);
reverse(res.begin(),res.end());
return res;
}
__intinf __intinf::operator-()const{
if(*this==0)return 0;
__intinf res=*this;res.flag=!flag;return res;
}
__intinf __intinf::operator~()const{return -(*this)-1;}
__intinf __intinf::abs()const{__intinf res=*this;res.flag=true;return res;}
__intinf __intinf::abs(const __intinf&a){return a.abs();}
int __intinf::_digit_len()const{return size;}
bool __intinf::operator==(const __intinf&x)const{return compare(x)==0;}
#if __cplusplus >= 202002L
auto __intinf::operator<=>(const __intinf&x)const{return compare(x);}
#else
bool __intinf::operator<(const __intinf&x)const{return compare(x)<0;}
bool __intinf::operator>(const __intinf&x)const{return compare(x)>0;}
bool __intinf::operator!=(const __intinf&x)const{return compare(x)!=0;}
bool __intinf::operator<=(const __intinf&x)const{return compare(x)<=0;}
bool __intinf::operator>=(const __intinf&x)const{return compare(x)>=0;}
#endif
__intinf __intinf::operator+(const __intinf&x)const{
if(!x.flag)return *this-x.abs();
if(!flag)return x-abs();
__intinf res;
res.flag=!(flag^x.flag);
int n=max(size,x.size)+1;
res.reserve(n);
digit_t carry=0;
for(int i=1;i<=n;i++){
digit_t d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
res.push(d1+d2+carry);
carry=res.digits[i]/BASE;
res.digits[i]%=BASE;
}
while(res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
__intinf __intinf::operator-(const __intinf&x)const{
if(!x.flag)return *this+x.abs();
if(!flag)return -(abs()+x);
__intinf res;
if(*this<x)res.flag=false;
digit_t carry=0;
int n=max(size,x.size);
res.reserve(n);
for(int i=1;i<=n;i++){
digit_t d1=i<=size?digits[i]:0,d2=i<=x.size?x.digits[i]:0;
if(res.flag)res.push(d1-d2-carry);
else res.push(d2-d1-carry);
if(res.digits[i]<0)res.digits[i]+=BASE,carry=1;
else carry=0;
}
while(res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
namespace __FFT{
constexpr long long FFT_BASE=1e4;
constexpr double PI2=6.283185307179586231995927;
constexpr double PI6=18.84955592153875869598778;
constexpr int RECALC_WIDTH=10;
constexpr int RECALC_BASE=(1<<RECALC_WIDTH)-1;
struct complex{
double real,imag;
complex(double x=0.0,double y=0.0):real(x),imag(y){}
complex operator+(const complex&other)const{return complex(real+other.real,imag+other.imag);}
complex operator-(const complex&other)const{return complex(real-other.real,imag-other.imag);}
complex operator*(const complex&other)const{return complex(real*other.real-imag*other.imag,real*other.imag+other.real*imag);}
complex&operator+=(const complex&other){return real+=other.real,imag+=other.imag,*this;}
complex&operator-=(const complex&other){return real-=other.real,imag-=other.imag,*this;}
complex&operator*=(const complex&other){return *this=*this*other;}
};
complex* arr=nullptr;
inline void init(int n){
if(arr!=nullptr)delete[] arr,arr=nullptr;
arr=new complex[n+1];
}
template<const int n>inline void fft(complex* a){
const int n2=n>>1,n4=n>>2;
complex w(1.0,0.0),w3(1.0,0.0);
const complex wn(cos(PI2/n),sin(PI2/n)),wn3(cos(PI6/n),sin(PI6/n));
for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
if(!(i&RECALC_BASE))w=complex(cos(PI2*i/n),sin(PI2*i/n)),w3=w*w*w;
complex x=a[i]-a[i+n2],y=a[i+n4]-a[i+n2+n4];
y=complex(y.imag,-y.real);
a[i]+=a[i+n2],a[i+n4]+=a[i+n2+n4];
a[i+n2]=(x-y)*w,a[i+n2+n4]=(x+y)*w3;
}
fft<n2>(a),fft<n4>(a+n2),fft<n4>(a+n2+n4);
}
template<>inline void fft<0>(complex*){}
template<>inline void fft<1>(complex*){}
template<>inline void fft<2>(complex* a){
complex x=a[0],y=a[1];
a[0]+=y,a[1]=x-y;
}
template<>inline void fft<4>(complex* a){
complex a0=a[0],a1=a[1],a2=a[2],a3=a[3];
complex x=a0-a2,y=a1-a3;
y=complex(y.imag,-y.real);
a[0]+=a2,a[1]+=a3,a[2]=x-y,a[3]=x+y;
fft<2>(a);
}
template<const int n>inline void ifft(complex* a){
const int n2=n>>1,n4=n>>2;
ifft<n2>(a),ifft<n4>(a+n2),ifft<n4>(a+n2+n4);
complex w(1.0,0.0),w3(1.0,0.0);
const complex wn(cos(PI2/n),-sin(PI2/n)),wn3(cos(PI6/n),-sin(PI6/n));
for(int i=0;i<n4;i++,w*=wn,w3*=wn3){
if(!(i&RECALC_BASE))w=complex(cos(PI2*i/n),-sin(PI2*i/n)),w3=w*w*w;
complex p=w*a[i+n2],q=w3*a[i+n2+n4];
complex x=a[i],y=p+q,x1=a[i+n4],y1=p-q;
y1=complex(y1.imag,-y1.real);
a[i]+=y,a[i+n4]+=y1,a[i+n2]=x-y,a[i+n2+n4]=x1-y1;
}
}
template<>inline void ifft<0>(complex*){}
template<>inline void ifft<1>(complex*){}
template<>inline void ifft<2>(complex* a){
complex x=a[0],y=a[1];
a[0]+=y,a[1]=x-y;
}
template<>inline void ifft<4>(complex* a){
ifft<2>(a);
complex p=a[2],q=a[3];
complex x=a[0],y=p+q,x1=a[1],y1=p-q;
y1=complex(y1.imag,-y1.real);
a[0]+=y,a[1]+=y1,a[2]=x-y,a[3]=x1-y1;
}
inline void dft(complex* a,int n){
if(n<=1)return;
switch(n){
case 1<<2:fft<1<<2>(a);break;
case 1<<3:fft<1<<3>(a);break;
case 1<<4:fft<1<<4>(a);break;
case 1<<5:fft<1<<5>(a);break;
case 1<<6:fft<1<<6>(a);break;
case 1<<7:fft<1<<7>(a);break;
case 1<<8:fft<1<<8>(a);break;
case 1<<9:fft<1<<9>(a);break;
case 1<<10:fft<1<<10>(a);break;
case 1<<11:fft<1<<11>(a);break;
case 1<<12:fft<1<<12>(a);break;
case 1<<13:fft<1<<13>(a);break;
case 1<<14:fft<1<<14>(a);break;
case 1<<15:fft<1<<15>(a);break;
case 1<<16:fft<1<<16>(a);break;
case 1<<17:fft<1<<17>(a);break;
case 1<<18:fft<1<<18>(a);break;
case 1<<19:fft<1<<19>(a);break;
case 1<<20:fft<1<<20>(a);break;
case 1<<21:fft<1<<21>(a);break;
case 1<<22:fft<1<<22>(a);break;
case 1<<23:fft<1<<23>(a);break;
case 1<<24:fft<1<<24>(a);break;
case 1<<25:fft<1<<25>(a);break;
case 1<<26:fft<1<<26>(a);break;
case 1<<27:fft<1<<27>(a);break;
case 1<<28:fft<1<<28>(a);break;
case 1<<29:fft<1<<29>(a);break;
case 1<<30:fft<1<<30>(a);break;
throw FFTLimitExceededError();
}
}
inline void idft(complex* a,int n){
if(n<=1)return;
switch(n){
case 1<<2:ifft<1<<2>(a);break;
case 1<<3:ifft<1<<3>(a);break;
case 1<<4:ifft<1<<4>(a);break;
case 1<<5:ifft<1<<5>(a);break;
case 1<<6:ifft<1<<6>(a);break;
case 1<<7:ifft<1<<7>(a);break;
case 1<<8:ifft<1<<8>(a);break;
case 1<<9:ifft<1<<9>(a);break;
case 1<<10:ifft<1<<10>(a);break;
case 1<<11:ifft<1<<11>(a);break;
case 1<<12:ifft<1<<12>(a);break;
case 1<<13:ifft<1<<13>(a);break;
case 1<<14:ifft<1<<14>(a);break;
case 1<<15:ifft<1<<15>(a);break;
case 1<<16:ifft<1<<16>(a);break;
case 1<<17:ifft<1<<17>(a);break;
case 1<<18:ifft<1<<18>(a);break;
case 1<<19:ifft<1<<19>(a);break;
case 1<<20:ifft<1<<20>(a);break;
case 1<<21:ifft<1<<21>(a);break;
case 1<<22:ifft<1<<22>(a);break;
case 1<<23:ifft<1<<23>(a);break;
case 1<<24:ifft<1<<24>(a);break;
case 1<<25:ifft<1<<25>(a);break;
case 1<<26:ifft<1<<26>(a);break;
case 1<<27:ifft<1<<27>(a);break;
case 1<<28:ifft<1<<28>(a);break;
case 1<<29:ifft<1<<29>(a);break;
case 1<<30:ifft<1<<30>(a);break;
throw FFTLimitExceededError();
}
}
}
__intinf __intinf::fft_mul(const __intinf&a,const __intinf&b){
int least=(a.size+b.size)<<1,lim=1<<__lg(least);
if(lim<least)lim<<=1;
__FFT::init(lim);
using __FFT::arr;
for(int i=0;i<a.size;i++){
arr[i<<1].real=a.digits[i+1]%10000;
arr[i<<1|1].real=a.digits[i+1]/10000%10000;
}
for(int i=0;i<b.size;i++){
arr[i<<1].imag=b.digits[i+1]%10000;
arr[i<<1|1].imag=b.digits[i+1]/10000%10000;
}
__FFT::dft(arr,lim);
for(int i=0;i<lim;i++)arr[i]*=arr[i];
__FFT::idft(arr,lim);
__intinf res;
res.resize(a.size+b.size+1);
digit_t carry=0;
double inv=0.5/lim;
for(int i=0;i<=a.size+b.size;i++){
carry+=(digit_t)(arr[i<<1].imag*inv+0.5);
carry+=(digit_t)(arr[i<<1|1].imag*inv+0.5)*10000LL;
res.digits[i+1]+=carry%BASE,carry/=BASE;
}
while(res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
__intinf __intinf::operator*(const __intinf&x)const{
__intinf zero=0;
if(*this==zero||x==zero)return zero;
int n=size,m=x.size;
if(1LL*n*m>=FFT_LIMIT){
__intinf res=fft_mul(*this,x);
res.flag=!(flag^x.flag);
return res;
}
__intinf res;
res.flag=!(flag^x.flag);
res.resize(n+m+2);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
res.digits[i+j-1]+=digits[i]*x.digits[j];
res.digits[i+j]+=res.digits[i+j-1]/BASE;
res.digits[i+j-1]%=BASE;
}
for(int i=1;i<=n+m+1;i++){
res.digits[i+1]+=res.digits[i]/BASE;
res.digits[i]%=BASE;
}
while(res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
__intinf&__intinf::operator*=(int x){
if(x==0||*this==0)return *this=0;
if(x<0)flag=!flag,x=-x;
digit_t carry=0;
for(int i=1;i<=size||carry;i++){
if(i>size)push(0);
digit_t cur=digits[i]*x+carry;
carry=cur/__intinf::BASE;
digits[i]=cur%__intinf::BASE;
}
while(size>1&&digits[size]==0)pop();
return *this;
}
__intinf __intinf::operator*(const int&x)const{__intinf t=*this;return t*=x;}
__intinf __intinf::div2()const{
__intinf res=*this;
for(int i=size;i>=1;i--){
if((res.digits[i]&1)&&(i>1))res.digits[i-1]+=BASE;
res.digits[i]>>=1;
}
while (res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
__intinf __intinf::operator/(const long long&x)const{
if(x==0)throw -1;
if(*this==0)return 0;
if(x==2)return div2();
if(x==-2){__intinf res=div2();res.flag=!res.flag;return res;}
__intinf res;
res.flag=!(flag^(x>=0));
digit_t cur=0,div=std::abs(x);
res.resize(size);
for(int i=size;i>=1;i--){
cur=cur*BASE+digits[i];
res.digits[i]=res.flag?(cur/div):(-cur/-div);
cur%=div;
}
while(res.size>1&&res.digits[res.size]==0)res.pop();
return res;
}
inline __intinf __intinf::_move_r(int d)const{
if(*this==0||d>=size)return 0;
if(d==0)return *this;
__intinf res;res.reserve(size-d+1);
for(int i=d+1;i<=size;i++)res.push(digits[i]);
return res;
}
inline __intinf __intinf::_move_l(int d)const{
if(*this==0)return 0;
if(d==0)return *this;
__intinf res;res.reserve(size+d+1);
for(int i=1;i<=d;i++)res.push(0);
for(int i=1;i<=size;i++)res.push(digits[i]);
return res;
}
__intinf __intinf::newton_inv(int n)const{
if(*this==0)throw ZeroDivisionError();
if(min(size,n-size)<=NEWTON_MIN_LEVEL){
__intinf a;a.resize(n+1);
memset(a.digits,0,sizeof(digit_t)*a.size);
a.digits[n+1]=1;
return a.divmod(*this,true).first;
}
int k=(n-size+2)>>1,k2=k>size?0:size-k;
__intinf x=_move_r(k2);
int n2=k+x.size;
__intinf y=x.newton_inv(n2),a=y+y,b=(*this)*y*y;
return a._move_l(n-n2-k2)-b._move_r(2*(n2+k2)-n)-1;
}
pair<__intinf,__intinf>__intinf::newton_div(const __intinf&x)const{
int k=size-x.size+2,k2=k>x.size?0:x.size-k;
__intinf x2=x._move_r(k2);
if(k2!=0)x2+=1;
int n2=k+x2.size;
__intinf u=(*this)*x2.newton_inv(n2);
__intinf q=u._move_r(n2+k2),r=(*this)-q*x;
while(r>=x)q+=1,r-=x;
return make_pair(q,r);
}
pair<__intinf,__intinf>__intinf::divmod(const __intinf&x,bool dis_newton)const{
static const int base=__intinf::BASE;
__intinf a=abs(),b=x.abs();
if(b==0)throw ZeroDivisionError();
if(a<b)return make_pair(0,flag?a:-a);
if(!dis_newton&&size>NEWTON_LIMIT)return newton_div(x);
int t=base/(x.digits[x.size]+1);
a*=t,b*=t;
int n=a.size,m=b.size;
__intinf q=0,r=0;
q.resize(n);
for(int i=n;i>=1;i--){
r*=base,r+=a.digits[i];
digit_t d1=m<r.size?r.digits[m+1]:0,d2=m-1<r.size?r.digits[m]:0;
int d=(d1*base+d2)/b.digits[m];
r-=b*d;
while(!r.flag)r+=b,d--;
q.digits[i]=d;
}
q.flag=!(flag^x.flag),r.flag=flag;
while(q.size>1&&q.digits[q.size]==0)q.pop();
return make_pair(q,r/t);
}
__intinf __intinf::operator/(const __intinf&x)const{return divmod(x).first;}
__intinf __intinf::operator%(const long long&x)const{
if(x==2||x==4||x==5)return digits[1]%x;
return *this-(*this/x*x);
}
__intinf __intinf::operator%(const __intinf&x)const{return divmod(x).second;}
__intinf __intinf::pow(const long long&x)const{
__intinf res=1,a=*this;
for(long long t=x;t!=0;a*=a,t>>=1)if(t&1)res*=a;
return res;
}
__intinf __intinf::pow(const long long&x,const __intinf&p)const{
__intinf res=1,a=*this%p;
for(long long t=x;t!=0;a=a*a%p,t>>=1)if(t&1)res=res*a%p;
return res;
}
__intinf __intinf::root(const long long&m)const{
if(*this==0||m==1)return *this;
if(m==2)return sqrt();
static constexpr long long base=__intinf::BASE;
__intinf n=*this,t=base,x0=min(n,t._move_l((n.size+m)/m));
long long l=0,r=base-1;
while(l<r){
long long mid=(l+r)>>1;
x0.digits[x0.size]=mid;
if(x0.pow(m)<=n)l=mid+1;
else r=mid;
}
x0.digits[x0.size]=l;
while(x0.size>1&& x0.digits[x0.size]==0)x0.pop();
__intinf x=(x0*(m-1)+n/x0.pow(m-1))/m;
while(x<x0)swap(x,x0),x=(x0*(m-1)+n/x0.pow(m-1))/m;
return x0;
}
__intinf __intinf::sqrt()const{
if(*this<=1)return *this;
static constexpr long long base=__intinf::BASE;
__intinf n=*this,x0=__intinf(base)._move_l((n.size+2)>>1);
__intinf x=(x0+n/x0).div2();
while (x<x0)swap(x,x0),x=(x0+n/x0).div2();
return x0;
}
__intinf __intinf::gcd(const __intinf&x)const{
__intinf a=*this,b=x;
if(a<b)swap(a,b);
if(b==0)return a;
int t=0;
while(a%2==0&&b%2==0)a=a.div2(),b=b.div2(),t++;
while(b>0){
if(a%2==0)a=a.div2();
else if(b%2==0)b=b.div2();
else a-=b;
if(a<b)swap(a,b);
}
while(t--)a+=a;
return a;
}
__intinf __intinf::lcm(const __intinf& x)const{return *this/gcd(x)*x;}
__intinf __intinf::pow(const __intinf&a,const long long&b){return a.pow(b);}
__intinf __intinf::pow(const __intinf&a,const long long&b,const __intinf&c){return a.pow(b,c);}
__intinf __intinf::root(const __intinf&a,const long long&b){return a.root(b);}
__intinf __intinf::sqrt(const __intinf&a){return a.sqrt();}
__intinf __intinf::gcd(const __intinf&a,const __intinf&b){return a.gcd(b);}
__intinf __intinf::lcm(const __intinf&a,const __intinf&b){return a.lcm(b);}
__intinf&__intinf::operator+=(const __intinf&x){return *this=*this+x;}
__intinf&__intinf::operator-=(const __intinf&x){return *this=*this-x;}
__intinf&__intinf::operator*=(const __intinf&x){return *this=*this*x;}
__intinf&__intinf::operator/=(const long long&x){return *this=*this/x;}
__intinf&__intinf::operator/=(const __intinf&x){return *this=*this/x;}
__intinf&__intinf::operator%=(const long long&x){return *this=*this/x;}
__intinf&__intinf::operator%=(const __intinf&x){return *this=*this%x;}
__intinf __intinf::operator<<(const long long&x){
if(x<=0)return *this;
__intinf res=*this;
for(long long i=1;i<=x;i++)res+=res;
return res;
}
__intinf __intinf::operator>>(const long long&x){
if(x<=0)return *this;
__intinf res=*this;
for(long long i=1;i<=x;i++)res=res.div2();
return res;
}
__intinf&__intinf::operator<<=(const long long&x){return *this=*this<<x;}
__intinf&__intinf::operator>>=(const long long&x){return *this=*this>>x;}
template<class F>inline __intinf __intinf::binary_op_helper(const __intinf&x,const __intinf&y,const F&func){
auto to_bin=[](__intinf x,int n)->vector<bool>{
if(x==0)return{0};
vector<bool>res;
__intinf t;
if(x>0)t=x;
else t=~x;
for(;t!=0;t=t.div2())
res.emplace_back(x>0?t.digits[1]&1:!(t.digits[1]&1));
while(res.size()<n)
if(x>0)res.emplace_back(0);
else res.emplace_back(1);
reverse(res.begin(),res.end());
return res;
};
__intinf u=x,v=y;
if(u.abs()<v.abs())swap(u,v);
vector<bool>a=u.to_binary();
int n=a.size();
vector<bool>b=to_bin(v,n);
vector<bool>res(n,0);
for(int i=n-1;i>=0;i--)res[i]=func(a[i],b[i]);
return res;
}
__intinf __intinf::operator&(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a&b;});}
__intinf __intinf::operator|(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a|b;});}
__intinf __intinf::operator^(const __intinf&x){return binary_op_helper(*this,x,[](bool a,bool b)->bool{return a^b;});}
__intinf&__intinf::operator&=(const __intinf&x){return *this=*this&x;}
__intinf&__intinf::operator|=(const __intinf&x){return *this=*this|x;}
__intinf&__intinf::operator^=(const __intinf&x){return *this=*this^x;}
__intinf&__intinf::operator++(){return *this+=1;}
__intinf __intinf::operator++(int){__intinf t=*this;return *this+=1,t;}
__intinf&__intinf::operator--(){return *this-=1;}
__intinf __intinf::operator--(int){__intinf t=*this;return *this-=1,t;}
}注意：
- 使用__intinf转二进制时有符号位（在
A[0]） - 使用二进制转__intinf时注意要写符号位