для любых двух натуральных чисел m и n , m ⋅ n - это куб, если есть положительные целые числа a и b , такие что:
- ( m = a и n = a² ) или
- ( m = a²b и n = ab² ) или
- ( m = a³ и n = b³ )
Если вы будете учитывать все входные данные, вы можете проверить, какие пары не могут быть добавлены вместе.
Существует несколько других способов проверить, является ли число идеальным кубом :
Возьмите куб root из значения. Затем округлите этот результат, чтобы получить его целочисленное значение. Затем увеличьте это округленное значение до третьей степени. Когда этот результат совпадает с исходным числом, этот номер является идеальным кубом. (Обратите внимание, что этот метод подвержен ошибке округления для больших целых чисел). См. здесь .
Цифровой root идеального куба равен 1, 8 или 9 (0). См. здесь .
Предварительно составьте список всех кубов в заданном диапазоне. См. здесь .
Основано на двоичном представлении (отлично для больших целых чисел): См. здесь
Далее вам нужно найти максимальное подмножество кардинальности, которое можно сложить в корзину.
Вы можете построить график, где каждый узел представляет входное число, а между два узла, если два числа могут быть добавлены вместе. Теперь найдите Maximum Clique (размер максимальной клики называется Clique Number графика).
Эквивалентно, вы можете добавить ребро между двумя узлы, если два числа не могут быть сложены вместе. Теперь найдите Максимальный независимый набор вершин .