- #include<iostream>
- #include<iomanip>
- #include<algorithm>
- #include<vector>
- #include<cstdio>
- #define NNN 1000000000
- #define nnn 9
- using namespace std;
- class unsigned_huge_int
- {
- public:
- const size_t size() const
- {
- return u.size();
- }
- friend const bool operator <(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- if(a.size()==b.size())
- {
- for(int i=a.size()-1;i>=0;--i){
- if(a.u[i]!=b.u[i])
- return a.u[i]<b.u[i];
- }
- return 0;
- }
- return a.size()<b.size();
- }
- friend const bool operator ==(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- if(a.size()==b.size())
- {
- for(int i=a.size()-1;i>=0;--i){
- if(a.u[i]!=b.u[i])
- return 0;
- }
- return 1;
- }
- return 0;
- }
- friend const bool operator <=(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- return a<b || a==b;
- }
- friend const bool operator >(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- return !(a<=b);
- }
- friend const bool operator >=(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- return !(a<b);
- }
- friend const bool operator !=(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- return a==b;
- }
- unsigned_huge_int()
- {
- u.clear();
- u.push_back(0);
- }
- unsigned_huge_int(const unsigned long long &number)
- {
- u.clear();
- u.push_back(number);
- refresh();
- }
- unsigned_huge_int(const string&original)
- {
- u.clear();
- for(int i=original.size()-1,j=0,p=1;i>=0;--i)
- {
- j+=(original[i]-'0')*p;
- p*=10;
- if((!i) || p==NNN)
- {
- u.push_back(j);
- j=0;
- p=1;
- }
- }
- }
- friend istream& operator >> (istream& os,unsigned_huge_int &ob)
- {
- string original;
- os>>original;
- ob=original;
- return os;
- }
- friend ostream& operator << (ostream& os,const unsigned_huge_int &ob)
- {
- os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1];
- for(int i=ob.size()-2;i>=0;--i)
- os<<setw(nnn)<<setfill('0')<<ob.u[i];
- return os;
- }
- friend const unsigned_huge_int operator +(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- unsigned_huge_int r;
- r.u.resize(max(a.size(),b.size()));
- for(int i=0;i<r.size();++i)
- {
- if(i<a.size())
- r.u[i]+=a.u[i];
- if(i<b.size())
- r.u[i]+=b.u[i];
- }
- r.refresh();
- return r;
- }
- const unsigned_huge_int d()
- {
- return *this+*this;
- }
- friend const unsigned_huge_int operator *(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- if(b==2)
- return a+a;
- unsigned_huge_int r;
- r.u.resize(a.size()+b.size());
- for(int i=0;i<a.size();++i)
- {
- for(int j=0;j<b.size();++j)
- {
- r.u[i+j]+=a.u[i]*b.u[j];
- }
- }
- r.refresh();
- return r;
- }
- friend const unsigned_huge_int operator -(const unsigned_huge_int &a,const unsigned_huge_int &b)
- {
- unsigned_huge_int r;
- const unsigned_huge_int *p1=&a,*p2=&b;
- if(*p1<*p2)
- swap(p1,p2);
- r.u.resize(p1->size());
- for(int i=0;i<r.size();++i)
- if(i<p2->size())
- r.u[i]+=p1->u[i]-p2->u[i];
- else
- r.u[i]+=p1->u[i];
- r.refresh();
- return r;
- }
- friend unsigned_huge_int sqrt(const unsigned_huge_int &a)
- {
- unsigned_huge_int left=0,right=a,mid=0;
- while(left+1<right)
- {
- mid=div(left+right);
- if(a<mid*mid)
- right=mid;
- else
- left=mid;
- }
- return left;
- }
- friend unsigned_huge_int div(unsigned_huge_int a)
- {
- for(int i=a.size()-1;i>=0;--i)//fixed:i不可以unsigned//
- {
- if(a.u[i]%2&&i>=1)
- {
-
- a.u[i-1]+=NNN;
- }
- a.u[i]/=2;
- // cout<<"{"<<a.u[i]<<"}";
- }
- a.refresh();
- return a;
- }
- private:
- vector<unsigned long long> u;
- void refresh()
- {
- for(int i=0;i<size();++i)
- {
- if(u[i]>=NNN)
- {
- if(i==size()-1)
- u.push_back(u[i]/NNN);
- else
- u[i+1]+=u[i]/NNN;
- u[i]%=NNN;
- }
- while(u[i]<0)
- {
- u[i]+=NNN;
- u[i+1]-=1;
- }
- }
- for(int i=size()-1;i!=0;--i)
- {
- if(u[i]==0&&size()!=1)
- {
- u.pop_back();
- }else{
- break;
- }
- }
- }
- };
-
-
-
- int main()
- {
- unsigned_huge_int a;
- cin>>a;
- cout<<sqrt(a);
- }