Данилкамастре

15.02.2021 04:29

Информатика

Есть ответ 👍

Алиса любит игры с формулами и недавно придумала такую игру: первый игрок загадывает два натуральных числа 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. Можете написать идею алгоритма или код (желательно на плюсах)

211

384

Посмотреть ответы 3

Ответы на вопрос:

Zcnayper

Информатика

4,4(29 оценок)

Вам нужно найти такие 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;

}

Сателла1

Информатика

4,4(36 оценок)

[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;}
Алиса любит игры с формулами и недавно придумала такую игру: первый игрок загадывает два натуральных

Алиса любит игры с формулами и недавно придумала такую игру: первый игрок загадывает два натуральных

qqwweerrqq

Информатика

4,5(19 оценок)

Информационная деятельность человека используется в жизни повседневно.

Примерами профессий, где человек работает с информацией, являются программист, экономист, преподаватель, статистик, бизнес-аналитик.

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

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