Деньги. Много денег

Задача простая, даже, пожалуй, детская: fregima привела более изящное доказательство решения, чем я.

Выложен ряд из N монет орлом вверх. На первом шаге переворачивают каждую монету, начиная с первой. На втором — каждую вторую, начиная со второй, на третьем — каждую третью, начиная с третьей, и так далее. На N-ом шаге переворачивают последнюю монету.

Требуется ответить, сколько монет будет лежать вверх решкой после того, как будет перевернута последняя монета. Решение должно быть в O(1), то есть количество вычислений не должно зависеть от числа монет N.

Комментарии не скрываю, так что в них вы можете неожиданно обнаружить ответ, поэтому рекомендую подумать, не заглядывая. Обсуждение, разумеется, всяко приветствуется.