Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <iostream>
- #include <set>
- #include <numeric>
- #include <queue>
- #include <map>
- #include <iomanip>
- #include <sstream>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- ull Sol1(ull a, ull b) {
- ull S = a * b;
- ull l = 0; // поддерживается инвариант, что (l * l) < S;
- ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
- while (l + 1 < r)
- {
- ull m = (l + r) / 2;
- if (m * m >= S)
- {
- r = m;
- }
- else {
- l = m;
- }
- }
- if ((ull)r * (ull)r == S) {
- return r;
- }
- return 0;
- }
- ull Sol2(ull a, ull b) {
- ull S = a * b;
- ull l = 0; // поддерживается инвариант, что (l * l) < S;
- ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
- if (l + 1 == r && r * r == S) {
- return r;
- }
- while (l + 1 < r)
- {
- ull m = (l + r) / 2;
- if (m * m == S)
- {
- return m;
- }
- if (m * m > S) {
- r = m;
- }
- else {
- l = m;
- }
- }
- return 0;
- }
- int main()
- {
- /*
- for (ull i = 1; i < 100000000000000; ++i) {
- for (ull j = 1; i * j <= 100000000000000; ++j) {
- if (Sol1(i, j) != Sol2(i, j)) {
- cout << i << ' ' << j << '\n' << Sol1(i, j) << '\n' << Sol2(i, j) << '\n';
- }
- }
- }
- */
- ull a, b;
- cin >> a >> b;
- ull S = a * b;
- ull l = 0; // поддерживается инвариант, что (l * l) < S;
- ull r = max(a, b); // поддерживается инвариант, что (r * r) >= S;
- if (l + 1 == r && r * r == S) {
- return r;
- }
- while (l + 1 < r)
- {
- ull m = (l + r) / 2;
- if (m * m == S)
- {
- cout << m;
- return;
- }
- if (m * m > S) {
- r = m;
- }
- else {
- l = m;
- }
- }
- cout << 0;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement