Ввести натуральное число N и вывести, сколько ∃ различных пар натуральных чисел A и B: A³+B³=N (с точностью до перестановки). Вещественные операции (например, кубический корень) рекомендуется использовать как можно реже.
87539319
87539319 — это 167³+436³, 228³+423³ и 255³+414³.
3
Подсказка 1. Ни A, ни B не могут быть больше кубического корня из N. Вот тут вещественной операцией можно и воспользоваться.
Подсказка 2. Далеко не все пары A, B, имеет смысл проверять. Достаточно эффективно применить линейное программирование.
Подсказка 3. Если алгоритм к задаче достаточно неочевидный, он обычно описан в т. н. «спойлере». Чтобы посмотреть спойлер, нажмите ссылку «Комментарии» в шапке страницы.
Спойлер:
Начнём с A=1, B=N**⅓. Если A³+B³ > N, будем уменьшать B на 1, в противном случае — увеличивать A на 1. Если равны, посчитаем это разложение. Как только A станет больше B, подсчёт закончим.