Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<algorithm>
- #include<iostream>
- #include<iomanip>
- #include<stdio.h>
- #include<bitset>
- #include<vector>
- #include<string>
- #include<queue>
- #include<cmath>
- #include<ctime>
- #include<stack>
- #include<map>
- #include<set>
- using namespace std;
- typedef long long LL;
- typedef long double LD;
- typedef vector<LL> BIG;
- typedef vector<int> VI;
- typedef pair<LL,LL> PLL;
- typedef pair<int,int> PII;
- #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
- #define B_E(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- #define S second
- #define F first
- inline void file() {
- #ifdef _WIN32
- srand(time(NULL));
- return;
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- if (0) {
- freopen(".in", "r", stdin);
- freopen(".out", "w", stdout);
- }
- }
- inline void read(int& n) {
- #define nxt h = getchar_unlocked()
- #define nxt h = getchar()
- char h; n = 0;
- for (nxt; h<'0' || h>'9'; nxt);
- for (; h>='0' && h<='9'; nxt)
- n = n*10 + h-'0';
- #undef nxt
- }
- const clock_t MAXT = (100*CLOCKS_PER_SEC)/1000;
- const int PX[8] = {0,0,1,-1,1,1,-1,-1},
- PY[8] = {-1,1,0,0,-1,1,1,-1},
- N = 1e5 + 10,
- INF = 1e9,
- LENB = 1,
- MOD = 1e9 + 7;
- const LL INFL = 1e18,
- BASE = 10,
- MODL = 1e9 + 7;
- const LD EPS = 1e-6;
- inline int rnd(int l = 0, int r = INF) {
- unsigned ans = 0;
- ans = (ans<<15) | rand();
- ans = (ans<<15) | rand();
- ans = (ans<<15) | rand();
- ans = (ans<<15) | rand();
- ans = (ans<<15) | rand();
- ans %= r-l+1;
- ans += l;
- return ans;
- }
- BIG a,b,x,y;
- inline void write(BIG a) {
- int pos = a.size() - 1;
- while ( !a[pos] && pos )
- --pos;
- while ( pos >= 0 )
- cout<<a[pos--]%BASE;
- }
- inline BIG mult(BIG a, LL b) {
- BIG c;
- c.PB( a[0]*b );
- for (int i=1; i<a.size(); ++i) {
- c.PB( a[i]*b + c[i-1]/BASE );
- c[i-1] %= BASE;
- }
- while ( c.back() >= BASE ) {
- LL x = c.back()/BASE;
- c.back() %= BASE;
- if (x) c.PB(x);
- }
- return c;
- }
- inline void read_long(BIG& a) {
- #define nxt h = getchar_unlocked()
- #define nxt h = getchar()
- a.clear();
- char h;
- for (nxt; h<'0' || h>'9'; nxt);
- for (; h>='0' && h<='9'; nxt)
- a.PB(h-'0');
- reverse( B_E(a) );
- #undef nxt
- }
- inline BIG mult_long(BIG a, BIG b) {
- int n = a.size()+b.size()+10;
- BIG c(n);
- for (int i=0; i<n; ++i)
- c[i] = 0;
- for (int i=0; i<a.size(); ++i) {
- LL x = 0;
- for (int j=0; j<b.size() || x; ++j) {
- LL s = c[i+j] + x;
- if ( j < b.size() )
- s += a[i] * b[j];
- c[i+j] = s % BASE;
- x = s / BASE;
- }
- }
- while ( !c.empty() && !c.back() )
- c.pop_back();
- return c;
- }
- inline BIG sum(BIG a, BIG b) {
- BIG c;
- int mx,mn;
- mx = max(a.size(),b.size());
- mn = min(a.size(),b.size());
- c.PB( a[0]+b[0] );
- for (int i=1; i<mx+1; ++i) {
- c.PB( c[i-1]/BASE );
- if ( a.size() > i )
- c.back() += a[i];
- if ( b.size() > i )
- c.back() += b[i];
- }
- for (LL& i:c)
- i %= BASE;
- return c;
- }
- inline LL short_mod(BIG& a, LL b) {
- LL ans = 0;
- for (int i=a.size()-1; i>=0; --i)
- ans = (ans*10 + a[i]) % b;
- return ans;
- }
- inline BIG short_div(BIG& a, LL b) {
- BIG c;
- LL s = 0;
- for (int i=a.size()-1; i>=0; --i) {
- s = s*10 + a[i];
- if ( s>=b || !c.empty() )
- c.PB(s/b);
- s %= b;
- }
- if ( c.empty() )
- c.PB(0);
- reverse(B_E(c));
- return c;
- }
- inline BIG subtr(BIG a, BIG b) {
- int n = a.size();
- while ( !b.empty() && !b.back() )
- b.pop_back();
- while ( b.size() < n )
- b.PB(0);
- for (LL& i:b)
- i = BASE - 1 - i;
- b[0]++;
- a = sum(a,b);
- a.pop_back();
- while ( !a.empty() && !a.back() )
- a.pop_back();
- if ( a.empty() )
- a.PB(0);
- return a;
- }
- inline int cmp(BIG a, BIG b) {
- while ( !a.empty() && !a.back() ) a.pop_back();
- while ( !b.empty() && !b.back() ) b.pop_back();
- if ( a.size() > b.size() )
- return +1;
- if ( a.size() < b.size() )
- return -1;
- int n = a.size();
- for (int i=n-1; i>=0; --i) {
- if ( a[i]>b[i] ) return +1;
- if ( a[i]<b[i] ) return -1;
- }
- return 0;
- }
- inline void long_div(BIG a, BIG b, BIG& x, BIG& y) {
- x.clear();
- y.clear();
- y.PB(0);
- int cnt;
- BIG s;
- for (int i=a.size()-1; i>=0; --i) {
- y = mult(y,10);
- s.clear();
- s.PB(a[i]);
- y = sum(y,s);
- for (cnt=0; cmp(y,b) >= 0; ++cnt)
- y = subtr(y,b);
- x.PB(cnt);
- }
- reverse(B_E(x));
- while ( !x.empty() && !x.back() )
- x.pop_back();
- }
- inline BIG sqr(BIG a) {
- return mult_long(a,a);
- }
- inline BIG long_sqrt(BIG a) {
- BIG s; s.PB(1);
- while ( cmp(a, mult(sqr(s),100) ) != -1 )
- s = mult(s,10);
- for (int i=s.size()-1; i>=0; --i) {
- while ( cmp(a, sqr(s) ) != -1 )
- ++s[i];
- --s[i];
- }
- return s;
- }
- int main()
- { file();
- read_long(a);
- write( long_sqrt(a) );
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement