Задача М240‍‍‍

По заданному $x$‍‍ значение $x^8$‍‍ можно найти за три арифметических действия: $x^2=x\cdot x$‍,‍ $x^4=x^2\cdot x^2$‍,‍ $x^8=x^4\cdot x^4$‍,‍ а $x^{15}$‍‍ — за пять действий: первые три — те же самые, затем $x^8\cdot x^8=x^{16}$‍‍ и $x^{16}:x=x^{15}$‍.‍ Покажите, что

1. $x^{1000}$‍‍ можно найти за 12 действий (умножений и делений);
2. для любого натурального $n$‍‍ значение $x^n$‍‍ можно найти не более чем за $\dfrac32\log_2 n+1$‍‍ действий.