Совершенные числа

Решал я тут одну задачу из раздела теории чисел про нахождение совершенных чисел.

В принципе, тривиальная задача. Элементарное разложение на множители.

Как я ее решал. Прочитав определение совершенных чисел (до этого я не знал про такие числа, и далее будет понятно, что это было моей главной проблемой) и поняв, что мне надо разложить число на множители, я написал что-то вроде:

bool is_perfect(long long n) {
  if (n == 1) return false;
  long long s = 1;
  long long q = sqrt((double)n);
  for (long long i = 2; i <= q; ++i) {
    if ((n % i) == 0) {
      s += i;
      if (n/i != i) s += n/i;
    }
  }
  return s == n;
}

...
  bool found = false;
  while (m <= n) {
    if (is_perfect(m)) {
      os << m << endl;
      found = true;
    }
    m += 1;
  }
  if (!found) os << "Absent" << endl;
...

Ничего оригинального. Работает на данных тестовых контрольных примерах. Прогоняю в системе. На одном из тестов мне сообщают, что программа работает более двух секунд, и это превышение данного временного лимита.

И только тут я смотрю на органичения задачи. А именно, что верхняя граница для N - это 5*10^18, то есть если при этом дать M=1, то мой цикл должен будет пробежать ~10^18 значений, что в отведенные на это 2 секунды явно не укладывается.

Почесав репу, я начал гуглить, так как идей по ускорению алгоритма не было.

Первый же поиск раскрыл мне суть проблемы - а сколько вообще есть таких совершенных чисел? Оказывается, что на интервале от 0 до 5*10^18 их всего-то восемь, и они уже давно вычислены!

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128

Поэтому вместо самостоятельного вычисления этих чисел надо просто найти, какие их этих восьми попадают в данный интервал [M, N]. Как говорится "Easy peasy lemon squeezy!".

Естественно, после этого решение успешно засабмитилось.

Мораль (кстати, верная не только для спортивного программирования) - начинать решение алгоритмической задачи следует с выяснения верхних ограничений входных данных, ибо чаще всего они подсказывают путь решения. Как это ни странно, почему-то вместо этого сразу хочется кодить, откладывая на потом осознание факта, что в ограничения-то программа не укладывается.

Мораль 2. Есть случаи, когда надо просто знать, как решать тот или иной тип задач. А знать это можно только хотя был раз их прорешав. Можно, конечно, и самому изобрести новый QuickSort с нуля, но это будет уже другая история.

P.S. Сейчас идет Google Gode Jam 2010.

В квалификации я решил полностью две задачи из трех, что достаточно для этого раунда. В раунде же 1 (я пробовал все его подтуры) я решал только одну задачу, что, увы, маловато.

Еще интересный момент. В подраунде Round 1B участвовал известный своим юным возрастом "спортивный" программист Геннадий Короткевич (третья позиция сверху таблице результатов). Я всегда очень люблю смотреть решения других людей. Поглядев на его решения, а был реально поражен тем, что они написаны на Дельфи! (а фактически на Паскале) (на Code Jam'е по статистике есть решения и на более "экзотических" языках типа BrainFuck'а или PostScript'а, но такие программы скорее всего сгенерированы из "традиционного" языка, и это уже иная тема). И эти решения кратки и понятны, и не используют различные шаблонные заготовки, которые в целом в ходу в спортивном программировании. Это еще одно подтверждение, что даже для алгоритмических задач "неудобный" язык не является проблемой в написании быстрой и понятной программы.

P.P.S. Один мой друг учавствовал в раунде 1, сидя с ноутом на полу в аэропорту через Wifi. Это не помешало ему получить 127-е место и проход в следующий раунд.