[mwz]

Iska, представить "количество раз" в двоичном виде и начать удваивать результат, сохраняя те промежуточные значения, где в двоичном представлении единицы -- а по достижении максимума слить все промежуточные результаты? Тогда время вычислений будет расти не как n (или даже хуже?), а как двоичный логарифм n.