Advertisement
Derga

Untitled

Apr 2nd, 2024
682
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #include <iostream>
  7. #include <set>
  8. #include <numeric>
  9. #include <queue>
  10. #include <map>
  11. #include <iomanip>
  12. #include <sstream>
  13.  
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18. typedef unsigned long long ull;
  19.  
  20. ull Sol1(ull a, ull b) {
  21.  
  22.     ull S = a * b;
  23.     ull l = 0; // поддерживается инвариант, что (l * l) < S;
  24.     ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
  25.     while (l + 1 < r)
  26.     {
  27.         ull m = (l + r) / 2;
  28.         if (m * m >= S)
  29.         {
  30.             r = m;
  31.         }
  32.         else {
  33.             l = m;
  34.         }
  35.     }
  36.  
  37.     if ((ull)r * (ull)r == S) {
  38.         return r;
  39.     }
  40.  
  41.     return 0;
  42. }
  43.  
  44. ull Sol2(ull a, ull b) {
  45.     ull S = a * b;
  46.     ull l = 0; // поддерживается инвариант, что (l * l) < S;
  47.     ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
  48.    
  49.     if (l + 1 == r && r * r == S) {
  50.         return r;
  51.     }
  52.  
  53.     while (l + 1 < r)
  54.     {
  55.         ull m = (l + r) / 2;
  56.         if (m * m == S)
  57.         {
  58.             return m;
  59.         }
  60.         if (m * m > S) {
  61.             r = m;
  62.         }
  63.         else {
  64.             l = m;
  65.         }
  66.     }
  67.    
  68.     return 0;
  69. }
  70.  
  71. int main()
  72. {
  73.     /*
  74.     for (ull i = 1; i < 100000000000000; ++i) {
  75.         for (ull j = 1; i * j <= 100000000000000; ++j) {
  76.             if (Sol1(i, j) != Sol2(i, j)) {
  77.                 cout << i << ' ' << j << '\n' << Sol1(i, j) << '\n' << Sol2(i, j) << '\n';
  78.             }
  79.         }
  80.     }
  81.     */
  82.  
  83.     ull a, b;
  84.     cin >> a >> b;
  85.  
  86.     ull S = a * b;
  87.     ull l = 0; // поддерживается инвариант, что (l * l) < S;
  88.     ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
  89.  
  90.     if (l + 1 == r && r * r == S) {
  91.         return r;
  92.     }
  93.  
  94.     while (l + 1 < r)
  95.     {
  96.         ull m = (l + r) / 2;
  97.         if (m * m == S)
  98.         {
  99.             cout << m;
  100.             return;
  101.         }
  102.         if (m * m > S) {
  103.             r = m;
  104.         }
  105.         else {
  106.             l = m;
  107.         }
  108.     }
  109.  
  110.     cout << 0;
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement