Advertisement
Guest User

Untitled

a guest
Oct 19th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.15 KB | None | 0 0
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<stdio.h>
  5. #include<bitset>
  6. #include<vector>
  7. #include<string>
  8. #include<queue>
  9. #include<cmath>
  10. #include<ctime>
  11. #include<stack>
  12. #include<map>
  13. #include<set>
  14. using namespace std;
  15. typedef long long LL;
  16. typedef long double LD;
  17. typedef vector<LL> BIG;
  18. typedef vector<int> VI;
  19. typedef pair<LL,LL> PLL;
  20. typedef pair<int,int> PII;
  21. #define PRINT(a) cerr<<#a<<" = "<<(a)<<'\n'
  22. #define B_E(a) a.begin(), a.end()
  23. #define PB push_back
  24. #define MP make_pair
  25. #define S second
  26. #define F first
  27. inline void file() {
  28.     #ifdef _WIN32
  29.         srand(time(NULL));
  30.         return;
  31.     #endif
  32.  
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36.  
  37.     if (0) {
  38.         freopen(".in",  "r", stdin);
  39.         freopen(".out", "w", stdout);
  40.     }
  41. }
  42. inline void read(int& n) {
  43.     #define nxt h = getchar_unlocked()
  44.     #define nxt h = getchar()
  45.     char h; n = 0;
  46.     for (nxt; h<'0' || h>'9'; nxt);
  47.     for (; h>='0' && h<='9'; nxt)
  48.         n = n*10 + h-'0';
  49.     #undef nxt
  50. }
  51.  
  52.  
  53.  
  54.  
  55. const clock_t MAXT = (100*CLOCKS_PER_SEC)/1000;
  56. const int   PX[8] = {0,0,1,-1,1,1,-1,-1},
  57.             PY[8] = {-1,1,0,0,-1,1,1,-1},
  58.             N = 1e5 + 10,
  59.             INF = 1e9,
  60.             LENB = 1,
  61.             MOD = 1e9 + 7;
  62. const LL    INFL = 1e18,
  63.             BASE = 10,
  64.             MODL = 1e9 + 7;
  65. const LD    EPS = 1e-6;
  66.  
  67. inline int rnd(int l = 0, int r = INF) {
  68.     unsigned ans = 0;
  69.     ans = (ans<<15) | rand();
  70.     ans = (ans<<15) | rand();
  71.     ans = (ans<<15) | rand();
  72.     ans = (ans<<15) | rand();
  73.     ans = (ans<<15) | rand();
  74.     ans %= r-l+1;
  75.     ans += l;
  76.     return ans;
  77. }
  78.  
  79. BIG a,b,x,y;
  80.  
  81.  
  82. inline void write(BIG a) {
  83.     int pos = a.size() - 1;
  84.     while ( !a[pos] && pos )
  85.         --pos;
  86.  
  87.     while ( pos >= 0 )
  88.         cout<<a[pos--]%BASE;
  89. }
  90.  
  91. inline BIG mult(BIG a, LL b) {
  92.     BIG c;
  93.     c.PB( a[0]*b );
  94.     for (int i=1; i<a.size(); ++i) {
  95.         c.PB( a[i]*b + c[i-1]/BASE );
  96.         c[i-1] %= BASE;
  97.     }
  98.  
  99.     while ( c.back() >= BASE ) {
  100.         LL x = c.back()/BASE;
  101.         c.back() %= BASE;
  102.         if (x) c.PB(x);
  103.     }
  104.     return c;
  105. }
  106.  
  107. inline void read_long(BIG& a) {
  108.     #define nxt h = getchar_unlocked()
  109.     #define nxt h = getchar()
  110.  
  111.     a.clear();
  112.     char h;
  113.     for (nxt; h<'0' || h>'9'; nxt);
  114.     for (; h>='0' && h<='9'; nxt)
  115.         a.PB(h-'0');
  116.     reverse( B_E(a) );
  117.  
  118.     #undef nxt
  119. }
  120.  
  121.  
  122.  
  123. inline BIG mult_long(BIG a, BIG b) {
  124.     int n = a.size()+b.size()+10;
  125.     BIG c(n);
  126.     for (int i=0; i<n; ++i)
  127.         c[i] = 0;
  128.  
  129.     for (int i=0; i<a.size(); ++i) {
  130.         LL x = 0;
  131.         for (int j=0; j<b.size() || x; ++j) {
  132.             LL s = c[i+j] + x;
  133.             if ( j < b.size() )
  134.                 s += a[i] * b[j];
  135.             c[i+j] = s % BASE;
  136.             x = s / BASE;
  137.         }
  138.     }
  139.  
  140.     while ( !c.empty() && !c.back() )
  141.         c.pop_back();
  142.  
  143.     return c;
  144. }
  145.  
  146. inline BIG sum(BIG a, BIG b) {
  147.     BIG c;
  148.     int mx,mn;
  149.     mx = max(a.size(),b.size());
  150.     mn = min(a.size(),b.size());
  151.  
  152.  
  153.     c.PB( a[0]+b[0] );
  154.     for (int i=1; i<mx+1; ++i) {
  155.         c.PB( c[i-1]/BASE );
  156.  
  157.         if ( a.size() > i )
  158.             c.back() += a[i];
  159.         if ( b.size() > i )
  160.             c.back() += b[i];
  161.     }
  162.  
  163.     for (LL& i:c)
  164.         i %= BASE;
  165.  
  166.     return c;
  167. }
  168.  
  169.  
  170.  
  171.  
  172.  
  173. inline LL short_mod(BIG& a, LL b) {
  174.     LL ans = 0;
  175.     for (int i=a.size()-1; i>=0; --i)
  176.         ans = (ans*10 + a[i]) % b;
  177.     return ans;
  178. }
  179.  
  180.  
  181. inline BIG short_div(BIG& a, LL b) {
  182.     BIG c;
  183.     LL s = 0;
  184.     for (int i=a.size()-1; i>=0; --i) {
  185.         s = s*10 + a[i];
  186.  
  187.         if ( s>=b || !c.empty() )
  188.             c.PB(s/b);
  189.         s %= b;
  190.  
  191.     }
  192.  
  193.     if ( c.empty() )
  194.         c.PB(0);
  195.     reverse(B_E(c));
  196.     return c;
  197.  
  198. }
  199.  
  200. inline BIG subtr(BIG a, BIG b) {
  201.     int n = a.size();
  202.     while ( !b.empty() && !b.back() )
  203.         b.pop_back();
  204.  
  205.     while ( b.size() < n )
  206.         b.PB(0);
  207.  
  208.     for (LL& i:b)
  209.         i = BASE - 1 - i;
  210.     b[0]++;
  211.  
  212.     a = sum(a,b);
  213.     a.pop_back();
  214.     while ( !a.empty() && !a.back() )
  215.         a.pop_back();
  216.     if ( a.empty() )
  217.         a.PB(0);
  218.  
  219.     return a;
  220. }
  221.  
  222.  
  223. inline int cmp(BIG a, BIG b) {
  224.     while ( !a.empty() && !a.back() ) a.pop_back();
  225.     while ( !b.empty() && !b.back() ) b.pop_back();
  226.  
  227.     if ( a.size() > b.size() )
  228.         return +1;
  229.  
  230.     if ( a.size() < b.size() )
  231.         return -1;
  232.  
  233.  
  234.     int n = a.size();
  235.     for (int i=n-1; i>=0; --i) {
  236.         if ( a[i]>b[i] ) return +1;
  237.         if ( a[i]<b[i] ) return -1;
  238.     }
  239.  
  240.     return 0;
  241. }
  242.  
  243.  
  244. inline void long_div(BIG a, BIG b, BIG& x, BIG& y) {
  245.     x.clear();
  246.     y.clear();
  247.     y.PB(0);
  248.     int cnt;
  249.     BIG s;
  250.  
  251.     for (int i=a.size()-1; i>=0; --i) {
  252.         y = mult(y,10);
  253.         s.clear();
  254.         s.PB(a[i]);
  255.         y = sum(y,s);
  256.  
  257.         for (cnt=0; cmp(y,b) >= 0; ++cnt)
  258.             y = subtr(y,b);
  259.  
  260.         x.PB(cnt);
  261.     }
  262.  
  263.     reverse(B_E(x));
  264.     while ( !x.empty() && !x.back() )
  265.         x.pop_back();
  266. }
  267.  
  268. inline BIG sqr(BIG a) {
  269.     return mult_long(a,a);
  270. }
  271.  
  272. inline BIG long_sqrt(BIG a) {
  273.     BIG s; s.PB(1);
  274.     while ( cmp(a, mult(sqr(s),100) ) != -1 )
  275.         s = mult(s,10);
  276.  
  277.     for (int i=s.size()-1; i>=0; --i) {
  278.         while ( cmp(a, sqr(s) ) != -1 )
  279.             ++s[i];
  280.         --s[i];
  281.     }
  282.  
  283.  
  284.     return s;
  285. }
  286.  
  287.  
  288. int main()
  289. { file();
  290.  
  291.     read_long(a);
  292.     write( long_sqrt(a) );
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement