Задача
Рассмотрим все целочисленные комбинации a^b для 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5:
2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125
Если их расположить в порядке возрастания, исключив повторения, мы получим следующую последовательность из 15 различных членов:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
Сколько различных членов имеет последовательность a^b для 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?
Замечания
Если вы думаете про лобовой метод, то нужно просто каждую степень тупо вычислить (с применением арифметики больших чисел, конечно) и потом так же тупо сравнить со всеми остальными, выкинув совпадения. Такое решение будет работать вполне быстро.
Но обратим внимание, что требуется только количество членов, а это намёк
на то, что считать их не нужно. Также не нужно располагать их по возрастанию, это никак не влияет на ответ.
Решение
Неуникальными членами будут такие, степени которых выражаются через степени других.
Например: 2^4 = 4^2, значит 4^2 выбрасываем. 2^6 = 4^3 = 8^2, значит их тоже выбрасываем.
Я сделал массив размером a * b, где хранятся 1 или 0 – признаки уникальности степени a^b. Программа сначала получилась такая, но работала неправильно:
Я размещаю её тут, потому что она достаточно проста, чтобы отследить основную идею.
Итак, я перебираю a и b, и если элемент map[a][b] ненулевой, значит эта степень пока ещё уникальна, и счётчик увеличивается. Далее я ищу делители степени b, и каждый найденный делитель p используется так: a^b это (a^p)^(b/p).
Если a^p вышло за пределы массива, перебор заканчивается. Иначе элемент массива с этим адресом помечается как неуникальный и далее он увеличивать счётчик не будет.
Загвоздка оказалась в том, что при верном подходе ответ был неправильный, и я не мог найти причину. В конце концов мне пришлось зарядить тяжёлую артиллерию больших чисел, тупо посчитать все значения, и затем тупо сравнить их. Я также установил максимальную степень 25, чтобы было меньше данных, распечатал все неуникальные степени и сверил с теми, которые получались в данном решении. И нашёл причину:
4^15 = 8^10
К примерно таким сочетаниям алгоритм оказался слеп и поэтому пропускал их. В самом деле, степень 4^15 не раскладывается на 8^10, тем не менее они равны. Что там происходит?
(2^2)^15 = (2^3)^10 = 2^30
На деле она раскладывается с основанием 2. Относительно a = 2 всё верно и должно было правильно посчитаться, но максимальная степень была задана как 25, и поэтому до 2^30 она дойти не могла. Аналогично, даже если максимальная степень будет 100, всё равно найдётся такая степень 2, которая будет больше чем 2^100.
Короче говоря, в массиве есть дополнительные степени a, которые присутствуют неявным образом. Например, вся линейка степеней 4 это (2^2)^b, вся линейка степеней 8 это (2^3)^b и т.д.
Новое решение
Я стал перебирать массив по a, но степени для a теперь не от 2 до N, а от 2 до N*N, то есть максимально возможная степень.
Я перебираю все делители каждой степени, как и раньше. Если a^p слишком большое, то перебор заканчивается, если же степень слишком большая, то увеличивается p.
Публикую текст без комментариев для экономии места, но по ссылке он с комментариями.
Ссылка на онлайн-компилятор языка C с текстом программы
Да, кстати, я не сделал задачи 27 и 28, потому что простые числа надоели, а про матричную спираль я делал что-то похожее тут:
Подборка всех задач: