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 | #44493138 | Utilizator | |
Fișier | numere_mari.cpp | Dimensiune | 5.62 KB |
Data încărcării | 28 August 2023, 22:27 | Scor / rezultat | 100 puncte |
numere_mari.cpp: In function 'void fft(ll, ll, std::complex<double>*)': numere_mari.cpp:10: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*(big_int&)': numere_mari.cpp:37:2914: warning: left operand of comma operator has no effect [-Wunused-value] class big_int{ll sign=1;string digs;public:big_int(const big_int &x){*this=x;}big_int(string a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(ll n){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}big_int(int n=0){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}bool operator<(big_int &b){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<(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==-1);}bool operator>(big_int &b){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>(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==1);}bool operator==(big_int &b){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 ==(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}return 1;}template <typename T>bool operator <=(T &b){return !(*this>b);}template <typename T>bool operator >=(T &b){return !(*this<b);}template <typename T>bool operator !=(T &b){return !(*this==b);}big_int operator-(){big_int rez=*this;rez.sign*=-1;return rez;}big_int abs(){big_int rez=*this;rez.sign=1;return rez;}big_int operator+(big_int &b){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(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs(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+(T b){big_int c(b);return *this+c;}template <typename T>void operator+=(T &b){*this=*this+b;}template <typename T>big_int operator-(T &b){big_int c(-b);c+=*this;return c;}template <typename T>void operator -=(T &b){*this=*this-b;}big_int operator*(big_int &b){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*(T b){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(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 *=(T &b){*this=*this*b;}big_int operator/(big_int &b){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/(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=abs(b);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 /=(T &b){*this=*this/b;}big_int operator%(big_int b){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%(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=std::abs(b);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template <typename T>void operator %=(T &b){*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,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:37:2929: warning: left operand of comma operator has no effect [-Wunused-value] class big_int{ll sign=1;string digs;public:big_int(const big_int &x){*this=x;}big_int(string a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(ll n){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}big_int(int n=0){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}bool operator<(big_int &b){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<(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==-1);}bool operator>(big_int &b){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>(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==1);}bool operator==(big_int &b){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 ==(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}return 1;}template <typename T>bool operator <=(T &b){return !(*this>b);}template <typename T>bool operator >=(T &b){return !(*this<b);}template <typename T>bool operator !=(T &b){return !(*this==b);}big_int operator-(){big_int rez=*this;rez.sign*=-1;return rez;}big_int abs(){big_int rez=*this;rez.sign=1;return rez;}big_int operator+(big_int &b){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(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs(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+(T b){big_int c(b);return *this+c;}template <typename T>void operator+=(T &b){*this=*this+b;}template <typename T>big_int operator-(T &b){big_int c(-b);c+=*this;return c;}template <typename T>void operator -=(T &b){*this=*this-b;}big_int operator*(big_int &b){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*(T b){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(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 *=(T &b){*this=*this*b;}big_int operator/(big_int &b){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/(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=abs(b);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 /=(T &b){*this=*this/b;}big_int operator%(big_int b){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%(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=std::abs(b);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template <typename T>void operator %=(T &b){*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,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:37:2810: warning: unused variable 'j' [-Wunused-variable] class big_int{ll sign=1;string digs;public:big_int(const big_int &x){*this=x;}big_int(string a){digs=a,reverse(digs.begin(),digs.end());if(digs.back()=='-')digs.pop_back(),sign=-1;}big_int(ll n){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}big_int(int n=0){if(n<0)sign=-1;n=std::abs(n);while(n)digs.push_back(n%10+'0'),n/=10;}bool operator<(big_int &b){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<(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==-1);}bool operator>(big_int &b){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>(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(sign*(i-'0')<(b%10)*sgn)ok=-1;if(sign*(i-'0')>(b%10)*sgn)ok=1;b/=10;}return (ok==1);}bool operator==(big_int &b){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 ==(T b){ll ok=0,sgn=1;if(b<0)sgn=-1;if(sign<sgn)return 1;if(sign>sgn)return 0;b=abs(b);for(char i:digs){if(i-'0'!=b%10)return 0;b/=10;}return 1;}template <typename T>bool operator <=(T &b){return !(*this>b);}template <typename T>bool operator >=(T &b){return !(*this<b);}template <typename T>bool operator !=(T &b){return !(*this==b);}big_int operator-(){big_int rez=*this;rez.sign*=-1;return rez;}big_int abs(){big_int rez=*this;rez.sign=1;return rez;}big_int operator+(big_int &b){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(aux%10))%10+'0'),aux=-rez.sign;else rez.digs.push_back(std::abs(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+(T b){big_int c(b);return *this+c;}template <typename T>void operator+=(T &b){*this=*this+b;}template <typename T>big_int operator-(T &b){big_int c(-b);c+=*this;return c;}template <typename T>void operator -=(T &b){*this=*this-b;}big_int operator*(big_int &b){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*(T b){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(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 *=(T &b){*this=*this*b;}big_int operator/(big_int &b){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/(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=abs(b);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 /=(T &b){*this=*this/b;}big_int operator%(big_int b){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%(T b){big_int rez=*this;if(b<0)rez.sign*=-1;ll p=digs.size()-1,aux=0;b=std::abs(b);while(p>=0)aux=aux*10+digs[p]-'0',p--,aux%=b;return aux;}template <typename T>void operator %=(T &b){*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,big_int a){string x=a.digs;reverse(x.begin(),x.end());if(a.sign==-1&&x!="0")out<<'-';out<<x;return out;}}; ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
1 | 0 secunde | OK. | 10 | 10 | Exemplu | |
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | OK. | 10 | 10 | ||
4 | 0 secunde | OK. | 10 | 10 | ||
5 | 0 secunde | OK. | 10 | 10 | ||
6 | 0 secunde | OK. | 10 | 10 | ||
7 | 0 secunde | OK. | 10 | 10 | ||
8 | 0 secunde | OK. | 10 | 10 | ||
9 | 0.392 secunde | OK. | 10 | 10 | ||
10 | 0 secunde | OK. | 10 | 10 | ||
Punctaj total | 100 |
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ă.