Question

Алиса любит игры с формулами и недавно придумала такую игру: первый игрок загадывает два натуральных числа a и b (натуральные числа — это целые числа, большие нуля), и сообщает второму игроку значения a+b и a⋅b. Задача второго игрока — назвать любые подходящие a и b или сказать, что первый игрок ошибся и такие значения не могли получиться. Сыграйте с Алисой в эту новую игру: по заданным x=a+b и y=a⋅b отгадайте, какие a и b могли быть изначально загаданы. Входные данные В первой строке воода дано число x, равное сумме двух загаданных чисел (2⩽x⩽10^9). Во второй строке задано число y, равное произведению двух загаданных чисел (1⩽y⩽10^17). Выходные данные Выведите через пробел такие натуральные a и b, для которых верно, что x=a+b и y=a⋅b. Если вариантов ответа несколько, выведите любой. Если такие натуральные a и b не существуют, выведите единственное число 0. Можете написать идею алгоритма или код (желательно на плюсах)

Answer 1

Вам нужно найти такие a и b, что a + b = x и ab = y. По теореме Виета a и b - корни уравнения $t^2-xt+y=0$. Находим дискриминант $D=x^2-4y$, если он отрицательный - у уравнения не то что натуральных, действительных решений нет. Если дискриминант неотрицательный, но не полный квадрат, то натуральных решений тоже нет. Иначе решения уравнения $(x\pm\sqrt D)/2$, если они натуральные - это и есть ответ.

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

#include <iostream>

#include <cmath>

long long isqrt(long long number) {

 long long answer = 0, left = 0, right = 1e9;

 while (left <= right) {  

   long long middle = (left + right) / 2;

   long long middle_squared = middle * middle;

   if (middle_squared == number) {

     return middle;

   } else if (middle_squared < number) {

     answer = middle;

     left = middle + 1;

   } else {

     right = middle - 1;

   }

 }

 return answer;

}

int main() {

 long long x, y;

 std::cin >> x >> y;

 auto d = x * x - 4 * y;

 if (d < 0) {

   std::cout << 0;

   return 0;

 }

 auto sqrt_d = isqrt(d);

 if (sqrt_d * sqrt_d != d) {

   std::cout << 0;

   return 0;

 }

 if ((x - sqrt_d) % 2 != 0) {

   std::cout << 0;

   return 0;

 }

 std::cout << (x - sqrt_d) / 2 << " " << (x + sqrt_d) / 2;

}

Answer 2

[Del me plz]

Подписываюсь под каждым словом объяснения @Nelle987.

Заданные значения x = a+b и y = ab - подходят под описание теоремы Виета. А значит, мы можем свести задачу к поиску корней квадратного уравнения в целых действительных числах.

Хочу дополнить ответ @Nelle987 другой реализацией целочисленного квадратного корня, работающего на этапе компиляции.

Код:

• #include <iostream>
• constexpr long long isqrt (long long value, long long sq = 1ll, long long dlt = 3ll){
•    return sq <= value ? isqrt(value, sq+dlt, dlt+2ll) : (dlt >> 1) - 1ll;
• }
• int main() {
•    long long x, y;
•    std::cin >> x >> y;
•    auto d = x * x - 4 * y;
•    if (d < 0) {
•        std::cout << 0;
•        return 0;
•    }
•    auto sqrt_d = isqrt(d);
•    if (sqrt_d * sqrt_d != d) {
•        std::cout << 0;
•        return 0;
•    }
•    if ((x - sqrt_d) % 2 != 0) {
•        std::cout << 0;
•        return 0;
•    }
•    std::cout << (x - sqrt_d) / 2 << " " << (x + sqrt_d) / 2;
•    return 0;
• }

Answer 3

Алиса предложила интересную игру, в которой первый игрок загадывает два натуральных числа a и b, а затем сообщает второму игроку значения a+b и a⋅b. Задача второго игрока состоит в том, чтобы назвать подходящие значения a и b или сказать, что первый игрок ошибся и такие значения не могли получиться.

Для решения этой задачи, нам нужно найти значения a и b, которые удовлетворяют условиям x=a+b и y=a⋅b, где x - сумма загаданных чисел, а y - их произведение.

Идея алгоритма:

1. Переберем все возможные значения a от 1 до x-1. 2. Для каждого значения a, найдем соответствующее значение b = x - a. 3. Проверим, выполняется ли условие y = a⋅b. 4. Если условие выполняется, то выведем найденные значения a и b. 5. Если ни одна комбинация a и b не удовлетворяет условию, выведем 0.

Пример кода на C++:

```cpp #include

int main() { int x, y; std::cin >> x >> y;

int a = 1; int b = x - a;

while (a <= b) { if (a * b == y) { std::cout << a << " " << b << std::endl; return 0; } a++; b = x - a; }

std::cout << 0 << std::endl; return 0; } ```

Пример работы программы:

Входные данные: ``` 7 12 ``` Выходные данные: ``` 3 4 ``` В данном примере, первый игрок загадал числа a=3 и b=4. Сумма этих чисел равна 7 (x), а их произведение равно 12 (y).

Надеюсь, это поможет вам сыграть в игру с Алисой! Если у вас возникнут еще вопросы, не стесняйтесь задавать.