Алиса любит игры с формулами и недавно придумала такую игру: первый игрок загадывает два натуральных числа 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. Можете написать идею алгоритма или код (желательно на плюсах)
Вам нужно найти такие a и b, что a + b = x и ab = y. По теореме Виета a и b - корни уравнения
. Находим дискриминант 
, если он отрицательный - у уравнения не то что натуральных, действительных решений нет. Если дискриминант неотрицательный, но не полный квадрат, то натуральных решений тоже нет. Иначе решения уравнения 
, если они натуральные - это и есть ответ.
У меня нет уверенности, что можно посчитать целый корень из большого натурального числа с стандартных функций, так что напишу свою реализацию на основе двоичного поиска.
#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;
}
[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;}