Решение к задаче 97

Очевидно, что от 1 до 1000000 всего тысяча квадратов (1000^2=1000000). Заметим, что если число является четвертой степенью, то оно является и квадратом (пусть n = m^4, тогда n = (m^2)^2). Поэтому если мы выкинем все квадраты от 1 до 10^6, то и выкинем все четвертые степени.

Очевидно, что от 1 до 10^6 всего сто кубов (100^3=1000000). У квадратов и кубов есть пересечения, поэтому если мы выкинем все квадраты и кубы, то какие-то числа мы выкинем два раза, например, 64 (64=8^2=4^3). Несложно показать, что если число является квадратом и кубом, то оно является шестой степенью (например, это следует из основной теоремы арифметики). Шестых степеней от 1 до миллиона, очевидно, 10 (10^6=1000000).

Итак, всего чисел 1000000, квадратов -- 1000, кубов -- 100. Поэтому от миллиона надо отнять число всех квадратов и всех кубов и прибавить количество тех чисел, которые мы отняли дважды, а именно шестые степени, которых 10. Тогда ответом будет 1000000-1000-100+10.

Ответ: 998910.