#include #include #include #include #include #include #include using namespace std; typedef vector VI; typedef long long LL; #define FOR(x,b,e) for(int x=(b);x<=(e);++x) #define FORD(x,b,e) for(int x=(b);x>=(e);--x) #define REP(x,n) for(int x=0;x<(n);++x) #define VAR(v,n) __typeof(n) v=(n) #define ALL(c) (c).begin(),(c).end() #define SIZE(x) (int)(x).size() #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define PB push_back #define ST first #define ND second /* ====== BIG INT CLASS FROM WARSAW LIBRARY ====== */ class Natural { static const int BASE = 100000000; static const int BASEDIGS = 8; int ndigs; int *digs; void init(int n,const int *d) { while(n>0 && d[n-1]==0) --n; ndigs=n; digs=new int[n]; for(int i=0;i= 0 int n=sh+ndigs; int d[n]; REP(i,sh) d[i]=0; REP(i,ndigs) d[i+sh]=digs[i]; return Natural(n,d); } public: /* konstruktory */ Natural(int x=0) { int d[2]; d[0]=x%BASE; d[1]=x/BASE; init(2,d); } Natural(const Natural& a) { init(a.ndigs,a.digs); } Natural(const char *s) { int n=strlen(s); int nd=n/BASEDIGS+1; int d[nd]; REP(i,nd) { d[i]=0; FORD(j,BASEDIGS-1,0) { int poz=i*BASEDIGS+j; if(poz=BASE) { d[i]-=BASE; ++d[i+1]; } } return Natural(n,d); } Natural &operator+=(const Natural& a) { return *this = *this + a; } /* odejmowanie */ Natural operator-(const Natural& a) const { // a <= *this int d[ndigs]; REP(i,ndigs) d[i]=digs[i]; REP(i,ndigs) { if (i < a.ndigs) d[i]-=a.digs[i]; if (d[i] < 0) { d[i]+=BASE; --d[i+1]; } } return Natural(ndigs,d); } Natural &operator-=(const Natural& a) { return *this = *this - a; } /* mnozenie liczb */ Natural operator*(const Natural& a) const { int n=ndigs+a.ndigs; int d[n]; REP(i,n) d[i]=0; REP(i,ndigs) { int p=0; REP(j,a.ndigs) { long long v=(long long)(digs[i])*a.digs[j]; int v1=v/BASE,v0=v%BASE; d[i+j]+=v0+p; p=v1+d[i+j]/BASE; d[i+j]%=BASE; } for(int j=i+a.ndigs;p>0;++j) { d[j]+=p; p=d[j]/BASE; d[j]%=BASE; } } return Natural(n,d); } Natural &operator*=(const Natural&a) { return *this = *this * a; } /* dzielenie liczb */ Natural operator/(const Natural& a) const { int n=max(ndigs-a.ndigs+1,0); int d[n]; Natural prod; FORD(i,n-1,0) { int l=0, r=BASE-1; while(la.ndigs) return false; FORD(i,ndigs-1,0) { if(digs[i]a.digs[i]) return false; } return false; } bool operator==(const Natural&a) const { if(ndigs!=a.ndigs) return false; REP(i,ndigs) { if(digs[i]!=a.digs[i]) return false; } return true; } bool operator>(const Natural&a) const { return a<*this; } bool operator<=(const Natural&a) const { return !(a<*this); } bool operator>=(const Natural&a) const { return !(*this