Problema | Numere Mari | Operații I/O | tastatură/ecran |
---|---|---|---|
Limita timp | 0.5 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #44494070 | Utilizator | |
Fișier | numere_mari.cpp | Dimensiune | 6.20 KB |
Data încărcării | 29 August 2023, 03:56 | Scor / rezultat | Eroare de compilare |
numere_mari.cpp: In function 'void fft(ll, ll, std::complex<double>*)': numere_mari.cpp:9:24: warning: unused variable 'i2' [-Wunused-variable] ll n=1<<m,i,j=0,i1,i2,l,l1,l2,k; ^ numere_mari.cpp: In member function 'big_int big_int::operator+(const big_int&) const': numere_mari.cpp:36:2599: error: invalid operands of types '__gnu_cxx::__enable_if<true, double>::__type {aka double}' and 'int' to binary 'operator%' class big_int{ll sign=1;string digs;public:big_int(){}big_int(const big_int&x){*this=x;}big_int(const string&a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(const int&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}big_int(const ll&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}operator ll()const{ll x=0,p=0;while(p<digs.size())x=x*10+digs[digs.size()-p-1]-'0',p++;return x;}bool operator<(const big_int&b)const{if(sign>b.sign)return 0;if(sign<b.sign)return 1;if(digs.size()*sign<b.digs.size()*sign)return 1;if(digs.size()*sign>b.digs.size()*sign)return 0;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]<sign*b.digs[i];return 0;}template<typename T>bool operator<(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b!=0)ok=-1;return(ok==-1);}bool operator>(const big_int&b)const{if(sign>b.sign)return 1;if(sign<b.sign)return 0;if(digs.size()*sign<b.digs.size()*sign)return 0;if(digs.size()*sign>b.digs.size()*sign)return 1;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]>sign*b.digs[i];return 0;}template<typename T>bool operator>(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b>0)ok=-1;return(ok==1);}bool operator==(const big_int&b)const{if(sign!=b.sign)return 0;if(digs.size()!=b.digs.size())return 0;for(ll i=0;i<digs.size();i++)if(digs[i]!=b.digs[i])return 0;return 1;}template<typename T>bool operator==(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}if(b>0)return 0;return 1;}template<typename T>bool operator<=(const T&b)const{return !(*this>b);}template<typename T>bool operator>=(const T&b)const{return!(*this<b);}template<typename T>bool operator !=(const T&b)const{return!(*this==b);}big_int operator-()const{big_int rez=*this;rez.sign*=-1;return rez;}big_int abs()const{big_int rez=*this;rez.sign=1;return rez;}big_int operator+(const big_int&b)const{ll aux=0,p=0;big_int rez(""),c=-b,x=b,y=*this;if(*this<c)rez.sign=-1;else rez.sign=1;do{if(p<digs.size())aux+=sign*(digs[p]-'0');if(p<b.digs.size())aux+=b.sign*(b.digs[p]-'0');p++;if(aux*rez.sign<0)rez.digs.push_back((10-std::abs<ll>(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs<ll>(aux%10)+'0'),aux/=10;}while(aux||p<digs.size()||p<b.digs.size());while(rez.digs.back()=='0'&&rez.digs.size()>=2)rez.digs.pop_back();return rez;}template<typename T>big_int operator+(const T&b)const{big_int c(b);return*this+c;}template<typename T>void operator+=(const T&b){*this=*this+b;}void operator++(int){*this+=1;}void operator++(){*this+=1;}void operator--(int){*this-=1;}void operator--(){*this-=1;}template<typename T>big_int operator-(const T&b)const{big_int c(-b);c+=*this;return c;}template<typename T>void operator-=(const T&b){*this=*this-b;}big_int operator*(const big_int&b)const{ll aux=0,m=0,n=max(digs.size(),b.digs.size()),X=1,i,j;big_int rez("");rez.sign=sign*b.sign;n=2*n+1;while(X<n)m++,X<<=1;n=X;vector<complex<double>>x(n,(0.0,0.0)),y(n,(0.0,0.0));for(i=0;i<digs.size();i++)x[i].real(digs[i]-'0');for(i=0;i<b.digs.size();i++)y[i].real(b.digs[i]-'0');fft(1,m,&x[0]);fft(1,m,&y[0]);for(i=0;i<n;i++)x[i]*=y[i];fft(-1,m,&x[0]);i=0;do{if(i<n)aux+=floor(x[i].real()+0.5),i++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(i<n||aux!=0);while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator*(const T&b)const{if(b>=LONG_MAX/10){big_int a(b);return(*this)*a;}big_int rez("");rez.sign=sign;ll p=0,aux=0;if(b<0)rez.sign*=-1;b=std::abs<ll>(b);do{if(p<digs.size())aux+=(digs[p]-'0')*b,p++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(p<digs.size()||aux>0);return rez;}template <typename T>void operator*=(const T&b){*this=*this*b;}big_int operator/(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1,c;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p],c=0;while(aux>=cc)c++,aux-=cc;rez.digs[p]=c+'0',p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator/(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',rez.digs[p]=aux/b+'0',p--,aux%=b;while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>void operator /=(const T&b)const{*this=*this/b;}big_int operator%(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p];while(aux>=cc)aux-=cc;p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return aux;}template<typename T>ll operator%(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template<typename T>void operator%=(const T&b)const{*this=*this%b;}friend istream&operator>>(istream&in,big_int&a){string x;in>>x;a=big_int(x);return in;}friend ostream&operator<<(ostream&out,const big_int&a){string x=a.digs;reverse(x.begin(),x.end());if(a.sign==-1&&x!="0")out<<'-';out<<x;return out;}}; ^ numere_mari.cpp: In member function 'big_int big_int::operator*(const big_int&) const': numere_mari.cpp:36:3408: warning: left operand of comma operator has no effect [-Wunused-value] class big_int{ll sign=1;string digs;public:big_int(){}big_int(const big_int&x){*this=x;}big_int(const string&a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(const int&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}big_int(const ll&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}operator ll()const{ll x=0,p=0;while(p<digs.size())x=x*10+digs[digs.size()-p-1]-'0',p++;return x;}bool operator<(const big_int&b)const{if(sign>b.sign)return 0;if(sign<b.sign)return 1;if(digs.size()*sign<b.digs.size()*sign)return 1;if(digs.size()*sign>b.digs.size()*sign)return 0;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]<sign*b.digs[i];return 0;}template<typename T>bool operator<(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b!=0)ok=-1;return(ok==-1);}bool operator>(const big_int&b)const{if(sign>b.sign)return 1;if(sign<b.sign)return 0;if(digs.size()*sign<b.digs.size()*sign)return 0;if(digs.size()*sign>b.digs.size()*sign)return 1;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]>sign*b.digs[i];return 0;}template<typename T>bool operator>(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b>0)ok=-1;return(ok==1);}bool operator==(const big_int&b)const{if(sign!=b.sign)return 0;if(digs.size()!=b.digs.size())return 0;for(ll i=0;i<digs.size();i++)if(digs[i]!=b.digs[i])return 0;return 1;}template<typename T>bool operator==(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}if(b>0)return 0;return 1;}template<typename T>bool operator<=(const T&b)const{return !(*this>b);}template<typename T>bool operator>=(const T&b)const{return!(*this<b);}template<typename T>bool operator !=(const T&b)const{return!(*this==b);}big_int operator-()const{big_int rez=*this;rez.sign*=-1;return rez;}big_int abs()const{big_int rez=*this;rez.sign=1;return rez;}big_int operator+(const big_int&b)const{ll aux=0,p=0;big_int rez(""),c=-b,x=b,y=*this;if(*this<c)rez.sign=-1;else rez.sign=1;do{if(p<digs.size())aux+=sign*(digs[p]-'0');if(p<b.digs.size())aux+=b.sign*(b.digs[p]-'0');p++;if(aux*rez.sign<0)rez.digs.push_back((10-std::abs<ll>(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs<ll>(aux%10)+'0'),aux/=10;}while(aux||p<digs.size()||p<b.digs.size());while(rez.digs.back()=='0'&&rez.digs.size()>=2)rez.digs.pop_back();return rez;}template<typename T>big_int operator+(const T&b)const{big_int c(b);return*this+c;}template<typename T>void operator+=(const T&b){*this=*this+b;}void operator++(int){*this+=1;}void operator++(){*this+=1;}void operator--(int){*this-=1;}void operator--(){*this-=1;}template<typename T>big_int operator-(const T&b)const{big_int c(-b);c+=*this;return c;}template<typename T>void operator-=(const T&b){*this=*this-b;}big_int operator*(const big_int&b)const{ll aux=0,m=0,n=max(digs.size(),b.digs.size()),X=1,i,j;big_int rez("");rez.sign=sign*b.sign;n=2*n+1;while(X<n)m++,X<<=1;n=X;vector<complex<double>>x(n,(0.0,0.0)),y(n,(0.0,0.0));for(i=0;i<digs.size();i++)x[i].real(digs[i]-'0');for(i=0;i<b.digs.size();i++)y[i].real(b.digs[i]-'0');fft(1,m,&x[0]);fft(1,m,&y[0]);for(i=0;i<n;i++)x[i]*=y[i];fft(-1,m,&x[0]);i=0;do{if(i<n)aux+=floor(x[i].real()+0.5),i++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(i<n||aux!=0);while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator*(const T&b)const{if(b>=LONG_MAX/10){big_int a(b);return(*this)*a;}big_int rez("");rez.sign=sign;ll p=0,aux=0;if(b<0)rez.sign*=-1;b=std::abs<ll>(b);do{if(p<digs.size())aux+=(digs[p]-'0')*b,p++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(p<digs.size()||aux>0);return rez;}template <typename T>void operator*=(const T&b){*this=*this*b;}big_int operator/(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1,c;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p],c=0;while(aux>=cc)c++,aux-=cc;rez.digs[p]=c+'0',p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator/(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',rez.digs[p]=aux/b+'0',p--,aux%=b;while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>void operator /=(const T&b)const{*this=*this/b;}big_int operator%(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p];while(aux>=cc)aux-=cc;p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return aux;}template<typename T>ll operator%(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template<typename T>void operator%=(const T&b)const{*this=*this%b;}friend istream&operator>>(istream&in,big_int&a){string x;in>>x;a=big_int(x);return in;}friend ostream&operator<<(ostream&out,const big_int&a){string x=a.digs;reverse(x.begin(),x.end());if(a.sign==-1&&x!="0")out<<'-';out<<x;return out;}}; ^ numere_mari.cpp:36:3423: warning: left operand of comma operator has no effect [-Wunused-value] class big_int{ll sign=1;string digs;public:big_int(){}big_int(const big_int&x){*this=x;}big_int(const string&a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(const int&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}big_int(const ll&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}operator ll()const{ll x=0,p=0;while(p<digs.size())x=x*10+digs[digs.size()-p-1]-'0',p++;return x;}bool operator<(const big_int&b)const{if(sign>b.sign)return 0;if(sign<b.sign)return 1;if(digs.size()*sign<b.digs.size()*sign)return 1;if(digs.size()*sign>b.digs.size()*sign)return 0;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]<sign*b.digs[i];return 0;}template<typename T>bool operator<(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b!=0)ok=-1;return(ok==-1);}bool operator>(const big_int&b)const{if(sign>b.sign)return 1;if(sign<b.sign)return 0;if(digs.size()*sign<b.digs.size()*sign)return 0;if(digs.size()*sign>b.digs.size()*sign)return 1;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]>sign*b.digs[i];return 0;}template<typename T>bool operator>(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b>0)ok=-1;return(ok==1);}bool operator==(const big_int&b)const{if(sign!=b.sign)return 0;if(digs.size()!=b.digs.size())return 0;for(ll i=0;i<digs.size();i++)if(digs[i]!=b.digs[i])return 0;return 1;}template<typename T>bool operator==(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}if(b>0)return 0;return 1;}template<typename T>bool operator<=(const T&b)const{return !(*this>b);}template<typename T>bool operator>=(const T&b)const{return!(*this<b);}template<typename T>bool operator !=(const T&b)const{return!(*this==b);}big_int operator-()const{big_int rez=*this;rez.sign*=-1;return rez;}big_int abs()const{big_int rez=*this;rez.sign=1;return rez;}big_int operator+(const big_int&b)const{ll aux=0,p=0;big_int rez(""),c=-b,x=b,y=*this;if(*this<c)rez.sign=-1;else rez.sign=1;do{if(p<digs.size())aux+=sign*(digs[p]-'0');if(p<b.digs.size())aux+=b.sign*(b.digs[p]-'0');p++;if(aux*rez.sign<0)rez.digs.push_back((10-std::abs<ll>(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs<ll>(aux%10)+'0'),aux/=10;}while(aux||p<digs.size()||p<b.digs.size());while(rez.digs.back()=='0'&&rez.digs.size()>=2)rez.digs.pop_back();return rez;}template<typename T>big_int operator+(const T&b)const{big_int c(b);return*this+c;}template<typename T>void operator+=(const T&b){*this=*this+b;}void operator++(int){*this+=1;}void operator++(){*this+=1;}void operator--(int){*this-=1;}void operator--(){*this-=1;}template<typename T>big_int operator-(const T&b)const{big_int c(-b);c+=*this;return c;}template<typename T>void operator-=(const T&b){*this=*this-b;}big_int operator*(const big_int&b)const{ll aux=0,m=0,n=max(digs.size(),b.digs.size()),X=1,i,j;big_int rez("");rez.sign=sign*b.sign;n=2*n+1;while(X<n)m++,X<<=1;n=X;vector<complex<double>>x(n,(0.0,0.0)),y(n,(0.0,0.0));for(i=0;i<digs.size();i++)x[i].real(digs[i]-'0');for(i=0;i<b.digs.size();i++)y[i].real(b.digs[i]-'0');fft(1,m,&x[0]);fft(1,m,&y[0]);for(i=0;i<n;i++)x[i]*=y[i];fft(-1,m,&x[0]);i=0;do{if(i<n)aux+=floor(x[i].real()+0.5),i++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(i<n||aux!=0);while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator*(const T&b)const{if(b>=LONG_MAX/10){big_int a(b);return(*this)*a;}big_int rez("");rez.sign=sign;ll p=0,aux=0;if(b<0)rez.sign*=-1;b=std::abs<ll>(b);do{if(p<digs.size())aux+=(digs[p]-'0')*b,p++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(p<digs.size()||aux>0);return rez;}template <typename T>void operator*=(const T&b){*this=*this*b;}big_int operator/(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1,c;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p],c=0;while(aux>=cc)c++,aux-=cc;rez.digs[p]=c+'0',p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator/(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',rez.digs[p]=aux/b+'0',p--,aux%=b;while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>void operator /=(const T&b)const{*this=*this/b;}big_int operator%(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p];while(aux>=cc)aux-=cc;p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return aux;}template<typename T>ll operator%(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template<typename T>void operator%=(const T&b)const{*this=*this%b;}friend istream&operator>>(istream&in,big_int&a){string x;in>>x;a=big_int(x);return in;}friend ostream&operator<<(ostream&out,const big_int&a){string x=a.digs;reverse(x.begin(),x.end());if(a.sign==-1&&x!="0")out<<'-';out<<x;return out;}}; ^ numere_mari.cpp:36:3305: warning: unused variable 'j' [-Wunused-variable] class big_int{ll sign=1;string digs;public:big_int(){}big_int(const big_int&x){*this=x;}big_int(const string&a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(const int&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}big_int(const ll&x){ll n=x;if(n<0)sign=-1;n=std::abs<ll>(n);do{digs.push_back(n%10+'0'),n/=10;}while(n);}operator ll()const{ll x=0,p=0;while(p<digs.size())x=x*10+digs[digs.size()-p-1]-'0',p++;return x;}bool operator<(const big_int&b)const{if(sign>b.sign)return 0;if(sign<b.sign)return 1;if(digs.size()*sign<b.digs.size()*sign)return 1;if(digs.size()*sign>b.digs.size()*sign)return 0;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]<sign*b.digs[i];return 0;}template<typename T>bool operator<(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b!=0)ok=-1;return(ok==-1);}bool operator>(const big_int&b)const{if(sign>b.sign)return 1;if(sign<b.sign)return 0;if(digs.size()*sign<b.digs.size()*sign)return 0;if(digs.size()*sign>b.digs.size()*sign)return 1;for(ll i=digs.size()-1;i>=0;i--)if(digs[i]!=b.digs[i])return sign*digs[i]>sign*b.digs[i];return 0;}template<typename T>bool operator>(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}if(b>0)ok=-1;return(ok==1);}bool operator==(const big_int&b)const{if(sign!=b.sign)return 0;if(digs.size()!=b.digs.size())return 0;for(ll i=0;i<digs.size();i++)if(digs[i]!=b.digs[i])return 0;return 1;}template<typename T>bool operator==(const T&x)const{ll ok=0,sgn=1;if(x<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;ll b=std::abs<ll>(x);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}if(b>0)return 0;return 1;}template<typename T>bool operator<=(const T&b)const{return !(*this>b);}template<typename T>bool operator>=(const T&b)const{return!(*this<b);}template<typename T>bool operator !=(const T&b)const{return!(*this==b);}big_int operator-()const{big_int rez=*this;rez.sign*=-1;return rez;}big_int abs()const{big_int rez=*this;rez.sign=1;return rez;}big_int operator+(const big_int&b)const{ll aux=0,p=0;big_int rez(""),c=-b,x=b,y=*this;if(*this<c)rez.sign=-1;else rez.sign=1;do{if(p<digs.size())aux+=sign*(digs[p]-'0');if(p<b.digs.size())aux+=b.sign*(b.digs[p]-'0');p++;if(aux*rez.sign<0)rez.digs.push_back((10-std::abs<ll>(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs<ll>(aux%10)+'0'),aux/=10;}while(aux||p<digs.size()||p<b.digs.size());while(rez.digs.back()=='0'&&rez.digs.size()>=2)rez.digs.pop_back();return rez;}template<typename T>big_int operator+(const T&b)const{big_int c(b);return*this+c;}template<typename T>void operator+=(const T&b){*this=*this+b;}void operator++(int){*this+=1;}void operator++(){*this+=1;}void operator--(int){*this-=1;}void operator--(){*this-=1;}template<typename T>big_int operator-(const T&b)const{big_int c(-b);c+=*this;return c;}template<typename T>void operator-=(const T&b){*this=*this-b;}big_int operator*(const big_int&b)const{ll aux=0,m=0,n=max(digs.size(),b.digs.size()),X=1,i,j;big_int rez("");rez.sign=sign*b.sign;n=2*n+1;while(X<n)m++,X<<=1;n=X;vector<complex<double>>x(n,(0.0,0.0)),y(n,(0.0,0.0));for(i=0;i<digs.size();i++)x[i].real(digs[i]-'0');for(i=0;i<b.digs.size();i++)y[i].real(b.digs[i]-'0');fft(1,m,&x[0]);fft(1,m,&y[0]);for(i=0;i<n;i++)x[i]*=y[i];fft(-1,m,&x[0]);i=0;do{if(i<n)aux+=floor(x[i].real()+0.5),i++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(i<n||aux!=0);while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator*(const T&b)const{if(b>=LONG_MAX/10){big_int a(b);return(*this)*a;}big_int rez("");rez.sign=sign;ll p=0,aux=0;if(b<0)rez.sign*=-1;b=std::abs<ll>(b);do{if(p<digs.size())aux+=(digs[p]-'0')*b,p++;rez.digs.push_back(aux%10+'0'),aux/=10;}while(p<digs.size()||aux>0);return rez;}template <typename T>void operator*=(const T&b){*this=*this*b;}big_int operator/(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1,c;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p],c=0;while(aux>=cc)c++,aux-=cc;rez.digs[p]=c+'0',p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>big_int operator/(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',rez.digs[p]=aux/b+'0',p--,aux%=b;while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return rez;}template<typename T>void operator /=(const T&b)const{*this=*this/b;}big_int operator%(const big_int&b)const{big_int rez=*this,aux,cc=b.abs();rez.sign=sign*b.sign;ll p=digs.size()-1;while(p>=0){aux.digs="0"+aux.digs,aux.digs[0]=digs[p];while(aux>=cc)aux-=cc;p--;}while(rez.digs.back()=='0'&&rez.digs.size()>1)rez.digs.pop_back();return aux;}template<typename T>ll operator%(const T&x)const{big_int rez=*this;if(x<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;ll b=std::abs<ll>(x);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template<typename T>void operator%=(const T&b)const{*this=*this%b;}friend istream&operator>>(istream&in,big_int&a){string x;in>>x;a=big_int(x);return in;}friend ostream&operator<<(ostream&out,const big_int&a){string x=a.digs;reverse(x.begin(),x.end());if(a.sign==-1&&x!="0")out<<'-';out<<x;return out;}}; ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Numere Mari face parte din a doua categorie. Pentru aceste probleme se folosește un program suport, furnizat de propunătorul problemei. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.