Количество делителей.

[frankenstein]

Добрый вечер.
Я решаю такую задачу, даны 10 чисел $a_1, a_2, ..., a_{10}$
Нужно определить сколько делителей у произведения этих чисел.
Т.е. количество делителей числа:
$a_1 \cdot a_2 \cdot ... \cdot a_{10}$
Конечно это задачу можно решить методом ДП.
Вот решение:

map<uint32_t, uint32_t> memo;
uint32_t F(uint32_t n)
{
   if (n == 1) return 1; /* 1 has only one divisor */
   if (memo.find(n) != memo.end())
      return memo[n];

   uint32_t d;
   for (d = 2; d < n; ++d)
      if (n%d)
         break;

   if (n == d)
      return (memo[n] = 2);
   else
      return (memo[n] = F(n/d)+F(d));
}

Но вот возникла проблема, дело в том что эти числа не менее $1$ и неболее $10^4$
Так что при считании произведения получается переполнение.

Ну так как эти 10 чисел - делители. То можно ли для каждого посчитать количество делителей, а потом их суммировать?
Некоторые из них могут быть равны, что делать в таком случае?

И вообще справедливо ли это утверждение что, если $a_1, a_2, ... a_{10}$ делители некого числа,
то количество делителей этого числа, равно сумме количества делителей каждого из его попарно различных
делителей.

-- 28.12.2013, 19:27 --

Да, сразу противоречие:
У 8-ми 4 делителя. А сумма кол-ва делителей делителей 8 равно 5. 2 и 4 скажем.
Но как тогда быть?

-- 28.12.2013, 19:30 --

И функция неверна тогда, похоже я совсем заплутал.

[helgui]

Просто сложить нельзя, т.к. множества делителей могут пересекаться и мы посчитаем какой-либо делитель несколько раз. Вместо этого каждое число можно факторизовать, сложить показатели степеней простых , тем самым получив факторизацию произведения. Теперь количество делителей посчитать будет просто.

[frankenstein]

helgui, извините, но я новичок. И не знаю что такое факторизация. Можете привести пример?

[helgui]

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

[frankenstein]

Факторизация - это разложение числа на произведение простых чисел.
Но как это поможет определить количество делителей числа?

[helgui]

Пример. $36=2^2 \cdot 3^2$

-- 28.12.2013, 20:08 --

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

[frankenstein]

helgui, получается, у 36 4 делителя?

[helgui]

Нет, у 36 девять делителей. Количество делителей однозначно определяется показателями степеней простых. И не равно их сумме. Мы суммируем показатели, чтобы узнать факторизацию произведения чисел. Например, $a = 2 \cdot 3, b = 2^3 \cdot 5$, тогда $c = ab = 2^4\cdot3 \cdot 5$

[frankenstein]

Но как вы это определили?

[helgui]

Я определил это, как $3\cdot 3$. Все, дальше сами. На вики есть статья про функцию количество делителей, она же $\tau$ или $ \sigma_0$

[_Ivana]

(Оффтоп)

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

[iifat]

Недопол. Вообще-то, для приведения к несократимой дроби нафиг не нужна факторизация.

[_Ivana]

Недопол. (C) Намекните, как можно сделать без факторизации.

[iifat]

Алгоритмом Евклида найти НОД же. Учтя при этом специфику чисел, если полезут совсем уж громадные числитель/знаменатель.

[_Ivana]

Уже понял, что вы Евклида предложите. Спасибо.

(Оффтоп)

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