@[Binah_cyc](/user/760171) [https://www.luogu.com.cn/paste/8sjfimqa](https://www.luogu.com.cn/paste/8sjfimqa)
by wzj0829 @ 2024-04-27 10:14:57
@[Binah_cyc](/user/760171) 猜你想找：压位高精。
```cpp
namespace BigInterger{
//You can use it just like int, but it is a little slower
//By using it, you should include iostream and vector
struct Int{
int sign;
std::vector<int>v;
inline Int():sign(1){}
inline Int(const std::string&s){*this=s;}
inline Int(const int&v){
char buf[21];
sprintf(buf,"%d",v);
*this=buf;
}
inline void zip(const int&unzip){
if(!unzip)
for(int i=0;i<v.size();++i)
v[i]=get_pos(i<<2)+ get_pos(i<<2|1)*10+get_pos(i<<2|2)*100+get_pos(i<<2|3)*1000;
else
for(int i=(v.resize(v.size()<<2),v.size()-1),a;~i;--i)
a=((i&3)>=2)?v[i>>2]/100:v[i>>2]%100,v[i]=(i&1)?a/10:a%10;
setsign(1,1);
}
inline int get_pos(const int&pos)const{return pos>=v.size()?0:v[pos];}
inline Int&setsign(const int&newsign,const int&rev){
while(v.size()>1&&!v.back())v.pop_back();
sign=(v.empty()||(v.size()==1&&!v[0]))?1:(rev?newsign*sign:newsign);
return *this;
}
inline std::string to_str()const{
Int b=*this;
std::string s;
for(int i=(b.zip(1),0);i<b.v.size();++i)
s+=(char)(*(b.v.rbegin()+i)^48);
return (sign<0?"-":"")+(s.empty()?"0":s);
}
inline bool absless(const Int&b)const{
if(v.size()!=b.v.size())return v.size()<b.v.size();
for(int i=v.size()-1;~i;--i)
if(v[i]!=b.v[i])return v[i]<b.v[i];
return false;
}
inline Int operator-()const{
Int c=*this;
c.sign=(v.size()>1||v[0])?-c.sign:1;
return c;
}
inline Int&operator=(const std::string&s){
if(s[0]=='-')
*this=s.substr(1);
else{
for(int i=(v.clear(),0);i<s.size();++i)
v.push_back(*(s.rbegin()+i)^48);
zip(0);
}
return setsign(s[0]=='-'?-1:1,sign=1);
}
inline bool operator<(const Int&b)const{
return sign!=b.sign?sign<b.sign:(sign==1?absless(b):b.absless(*this));
}
inline bool operator==(const Int&b)const{return v==b.v&&sign==b.sign;}
inline Int&operator+=(const Int&b){
if(sign!=b.sign)return *this=(*this)-(-b);
v.resize(std::max(v.size(),b.v.size())+1);
for(int i=0,carry=0;i<b.v.size()||carry;++i){
carry+=v[i]+b.get_pos(i);
v[i]=carry%10000,carry/=10000;
}
return setsign(sign,0);
}
inline Int operator+(const Int&b)const{
Int c=*this;
return c+=b;
}
inline Int operator++(){return *this+=1;}
inline Int operator-(const Int&b)const{
if(b.v.empty()||b.v.size()==1&&!b.v[0])return *this;
if(sign!=b.sign)return (*this)+(-b);
if(absless(b))return -(b-*this);
Int c;
for(int i=0,borrow=0;i<v.size();++i){
borrow+=v[i]-b.get_pos(i);
c.v.push_back(borrow);
c.v.back()-=10000*(borrow>>=31);
}
return c.setsign(sign,0);
}
inline Int operator-=(const Int&b){return *this=*this-b;}
inline Int operator--(){return *this-=1;}
inline void add_mul(const Int&b,int mul){
v.resize(std::max(v.size(),b.v.size())+2);
for(int i=0,carry=0;i<b.v.size()||carry;++i){
carry+=v[i]+b.get_pos(i)*mul;
v[i]=carry%10000,carry/=10000;
}
}
inline Int operator*(const Int&b)const{
if(b<*this)return b*(*this);
Int c,d=b;
for(int i=0;i<v.size();++i,d.v.insert(d.v.begin(),0))
c.add_mul(d,v[i]);
return c.setsign(sign*b.sign,0);
}
inline Int operator*=(const Int&b){return *this=*this*b;}
inline Int operator/(const Int&b)const{
if(b.v.size()==1&&!b.v[0]){
std::cout<<"Divisor is 0.\nCheck your code now.\n";
exit(0);
return 0x7fffffff;
}
Int c,d;
d.v.resize(v.size());
double db=1.0/(b.v.back()+(b.get_pos((unsigned)b.v.size()-2)/1e4)+(b.get_pos((unsigned)b.v.size()-3)+1)/1e8);
for(int i=v.size()-1;~i;--i){
c.v.insert(c.v.begin(),v[i]);
int m=(c.get_pos(b.v.size())*10000+c.get_pos((int)b.v.size()-1))*db;
c-=b*m,c.setsign(c.sign,0),d.v[i]+=m;
while(c>=b)c-=b,++d.v[i];
}
return d.setsign(sign*b.sign,0);
}
inline Int operator/=(const Int&b){return *this=*this/b;}
inline Int operator%(const Int&b)const{return *this-*this/b*b;}
inline Int operator%=(const Int&b){return *this=*this%b;}
inline bool operator>(const Int&b)const{return b<*this;}
inline bool operator<=(const Int&b)const{return !(b<*this);}
inline bool operator>=(const Int&b)const{return !(*this<b);}
inline bool operator!=(const Int&b)const{return !(*this==b);}
};
inline std::istream& operator>>(std::istream& stream,Int&x){
std::string str;
stream>>str;
x=str;
return stream;
}
inline std::ostream& operator<<(std::ostream& stream,const Int&x){
stream<<x.to_str();
return stream;
}
}using BigInterger::Int;
```
by Super_Cube @ 2024-04-27 10:20:24
@[Binah_cyc](/user/760171) 压9位+FFT高精：https://www.luogu.com.cn/article/p6un33cl
by stripe_python @ 2024-04-27 10:23:28
谢谢，已关，此帖结。
by Binah_cyc @ 2024-04-27 10:46:31