1 Тема от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Тема: Задачи по теории чисел, по-моему

(1 задача)
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N. ограничения M и N могут достигать до 5*10^18

(2 задача)
Какое наименьшее число N можно представить в виде произведения N = A?B ровно K способами? Произведения A?B и B?А считаются одним

способом, все числа натуральные (1?K?50).

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Задачи по теории чисел, по-моему

А на вторую перебор+массив констант (либо даже без него) не пройдет? Можно делать либо совсем тупой перебор (просто перебирать все числа, начиная от 1 и находить количество делителей, не превышающих корень), а можно заметить что максимальное простое там будет небольшим, а так же тот факт, что если простое число присутствует в разложении, то все простые, меньшие его тоже присутствуют в нем.
Думаю, если делать перебор вторым способом, то даже массив констант не понадобится.

3 Ответ от Seyaua

  • Seyaua
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-16
  • Сообщений: 7

Re: Задачи по теории чисел, по-моему

1) Cовершенных чисел найдено совсем немного, поэтому тут можно забить массив констант из нескольких чисел. Как видно из http://www.research.att.com/~njas/sequences/A000396 уже 9-ое совершенное число существенно превосходит 5*10^18.

2) Лишь для чисел 31, 37, 47 ответ превышает 6*10^6. Для остальных чисел можно найти ответы перебором. Для трех чисел, для которых перебор ответа не найдет, легко можно найти ответы вручную. Достаточно воспользоваться тем фактом, что если число А представимо в виде A=p1^a1*p2^a2*...*pk^ak, то A имеет ровно (a1+1)*(a2+1)*...*(ak+1) делителей. Как выше заметил KADR, числа p1, p2, ..., pk должны быть последовательными простыми числами, причем p1=2, если мы хотим добиться минимальности ответа.