Решать задачу про квадрат

Question

Вот такая задача: Вася учится в одной из деревенских школ и мечтает стать агрономом, поэтому на уроке геометрии он научился вычислять площадь прямоугольника. Вася хочет определить, равна ли площадь прямоугольной области площади квадрата. Желательная информация:

Входной файл содержит два a, b (1<=a, b <= 10 ^ {18}) натуральные числа представляют ширину и высоту прямоугольной области соответственно.

Исходящие данные: В выходном файле, если квадрат равен площади поверхности, выведите эту сторону квадрата, иначе -1.

Я попробовал вот эта, но не получается:

#include <iostream>
#include <algorithm>
unsigned long long a, b, d;
int main() {
    std::cin >> a >> b;

    if (a == b) {
        std::cout << a;
        return 0;
    }

    if (a > b)
        std::swap(a, b);

    d = a * b;

    while (a <= b) {
        unsigned long long mid = a + (b - a) / 2;

        if (mid * mid == d) {
            std::cout << mid;
            return 0;
        }
        if (mid * mid < d)
            a = mid + 1;
        else
            b = mid - 1;
    }

    std::cout << -1;

    return 0;
}

Что я не учел? Заранее спасибо.

Answer 1

У Вас какой то странный алгоритм поиска квадрата. Но в любом случае, a и b могут быть до 10 в 18, значит их произведение - 10 в 36, а это выходит за пределы 64бит. Что делать? Попробовать разложить на множители оба числа (примеры разложения можно найти здесь Нахождение всех множителей большого числа в заданном диапазоне). Теперь просто смотрим на множители и каждого с них должно быть четное количество (после объединения множителей).

Второй способ - просто использовать любую библиотеку для длинной арифметики, которая умеет извлекать корень.

Третий способ - если это gcc/clang, то там есть тип __int128 - 128 битное число. Как раз то, что нужно. И весь код стает простейшим

__int128 d = a*b;
__int128 d2 = sqrt(d);
if (d2*d2 == d) { std::cout << "это квадрат!";}

---- upd ----

Набросал небольшой пример, который показывает, как проверить квадрат через делители. его можно ускорить, но это PoC

#include <iostream>
#include <map>


std::map<int, int> ff(long long int a) {
    std::map<int, int> r;
    int x = 2;
    while (a > 1 && a >= x) {
        int c = 0;
        while (a % x == 0) { a = a / x; c++;}
        r[x] = c;
        x++;
    }
    return r;
}


template <typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::map<K,V>& m) {
    os << "[";
    for (const auto el : m) {
        os << "{ " << el.first << "->" << el.second << "}"; 
    }
    os << "]";
    return os;
}

int main()
{
    int a = 20;
    int b = 125;
    auto a1 = ff(a);
    auto a2 = ff(b);
    std::cout << a1 << "\n";
    std::cout << a2 << "\n";
    for(const auto & el : a2) {
        a1[el.first] += el.second;
    }
    // теперь a1 содержит все делители их количество для произведения a*b
    std::cout << a1 << "\n";
    bool t = true;
    for (const auto & el : a1) {
        if (el.second % 2 != 0) { t = false; break;}
    }
    if (t) {
        std::cout << "it is square ";
        int d = 1;
        for (const auto & el : a1) {
            for (int i = 0; i < el.second / 2; i++) {
                d*= el.first;
            }
        }
        std::cout << d << "\n";
    }
    else {
        std::cout << "it is not square\n";
    }
}

Answer 2

Вы не учли что ab, который может достигать (10^18)^2, не помещается в 64 бита (2^64 < 2 * 10^19). Надо придумать способ решить задачу без умножения a на b.

Как проверить что произведение ab является полным квадратом, если нет возможности его вычислить? Пусть g = НОД(a, b) тогда ab = g^2(a / g)(b / g). В этом произведении множители a / g и b / g взаимно простые. ab - полный квадрат тогда и только тогда когда оба a / g и b / g - полные квадраты.

Вычисление НОД и проверка частных на "полные квадраты" не требует переменных двойной точности. Для проверки на полный квадрат точно (двоичным поиском) вычисляется целая часть корня квадратного, которая возводится в квадрат, который сравнивается с исходным числом.

#include <iostream>

uint64_t gcd(uint64_t a, uint64_t b) {
    while (b > 0) {
        uint64_t m = a % b;
        a = b;
        b = m;
    }
    return a;
}

uint64_t isqrt(uint64_t a) {
    uint64_t low = 0;
    uint64_t high = 1;
    while (high * high <= a) {
        low = high;
        high *= 2;
    }

    while (low < high - 1) {
        uint64_t mid = (low + high) / 2;
        if (mid * mid > a) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return low;
}

int main()
{
    uint64_t a, b;
    if (!(std::cin >> a >> b)) {
        return 1;
    }

    uint64_t g = gcd(a, b);

    uint64_t a2 = a / g;
    uint64_t a2sqrt = isqrt(a2);
    if (a2sqrt * a2sqrt != a2) {
        std::cout << -1 << '\n';
        return 0;
    }

    uint64_t b2 = b / g;
    uint64_t b2sqrt = isqrt(b2);
    if (b2sqrt * b2sqrt != b2) {
        std::cout << -1 << '\n';
        return 0;
    }

    std::cout << a2sqrt * b2sqrt * g << '\n';
}

БЛОГ НА HUSL

Решать задачу про квадрат

Ответы (2 шт):