Advertisement
Guest User

Untitled

a guest
Oct 18th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.58 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <stdint.h>
  4. #include <inttypes.h>
  5. #include <limits.h>
  6.  
  7. const long long lim = (USHRT_MAX * 1LL + 1LL) * (UINT_MAX * 1LL + 1LL);
  8. const long long st = UINT_MAX * 1LL + 1LL;
  9. long long f(long long x)
  10. {
  11.     long long l, r;
  12.     l = 0;
  13.     r = st / 2;
  14.     while(r - l > 1LL)
  15.     {
  16.         long long m = (l + r) >> 1;
  17.         if(m * m > x)
  18.         {
  19.             r = m;
  20.         }
  21.         else
  22.         {
  23.             if(m * m < x)
  24.             {
  25.                 l = m;
  26.             }
  27.             else
  28.             {
  29.                 r = m;
  30.                 break;
  31.             }
  32.         }
  33.     }
  34.     if(l * l > x)
  35.     {
  36.         r = l;
  37.     }
  38.     return (r - 1) * x;
  39.  
  40. }
  41. int main(void)
  42. {
  43.     long long x, p;
  44.     scanf("%lli", &x);
  45.     long long ans = -1;
  46.     for(p = x; p < lim; p += st)
  47.     {
  48.         long long l = 0;
  49.         long long r = st - 1LL;
  50.         while(r - l > 1LL)
  51.         {
  52.             long long m = (l + r) >> 1LL;
  53.             long long a = f(m);
  54.             if(a > p)
  55.             {
  56.                 r = m;
  57.             }
  58.             else
  59.             {
  60.                 if(a < p)
  61.                 {
  62.                     l = m;
  63.                 }
  64.                 else
  65.                 {
  66.                     r = m;
  67.                     break;
  68.                 }
  69.             }
  70.         }
  71.         if(p == f(l))
  72.         {
  73.             ans = l;
  74.             break;
  75.         }
  76.         if(p == f(r))
  77.         {
  78.             ans = r;
  79.             break;
  80.         }
  81.     }
  82.     printf("%lli\n", ans);
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement