Числа Каталана по модулю некого числа

[frankenstein]

Добрый день.
Дана рекуррентно определенная последовательность
$ C_0 = 1$
$ C_{n+1} = \frac{2(2n+1)}{n+2} \cdot C_n$

Мне нужно посчитать $C_{1000} \mod 10000$.
Не обязательно ведь использовать длинную арифметику.
Я могу сделать так: как только очередное значение $C_i$
становится больше $10000$, я вместо этого числа беру
остаток от деления его на $10000$
Вот не знаю как дальше правильно продолжить.

[Sonic86]

frankenstein в сообщении #939136 писал(а):

Я могу сделать так: как только очередное значение $C_i$
становится больше $10000$, я вместо этого числа беру
остаток от деления его на $10000$

Нет, не можете.

Можно попробовать начать с вычисления $v_p(C_n)$ для $p=2;5$.

[frankenstein]

А что за функция $v_p$?

[nnosipov]

$\nu_p(N)$ --- это показатель, с которым простое $p$ входит в каноническое разложение $N$.

[frankenstein]

Нет, если следовать вашим указаниям получается сложно.
Я уверен что здесь можно применить эту формулу:

$$ (a_0 \cdot a_1 \cdot ... \cdot a_m) \mod n = ((a_0\mod n) \cdot (a_1\mod n) \cdot ... \cdot (a_m\mod n)) \mod n $$

[Cash]

Не забывайте, что в формуле присутствует и деление. А это совсем другой коленкор...

[demolishka]

frankenstein в сообщении #939184 писал(а):

Я уверен что здесь можно применить эту формулу:

Применить то можно, но вот коэффициент $\frac{2(2n+1)}{n+2}$ - дробный и вам придется искать $\frac{1}{n+2}$ по модулю 10000, то есть обратный элемент для $n+2$ в кольце по модулю 10000. Проблема в том, что 10000 - составное число и факторкольцо по нему полем не является, а это значит, что не все элементы обратимы (обратимы только те элементы, которые взаимно просты с 10000).

[ИСН]

Есть быстрые методы нахождения чисел Каталана без деления, но они очень медленные.

[Cash]

(Оффтоп)

ИСН, напомнило следующее
Элементарное доказательство теоремы Дирихле, предложенное Сельбергом, чрезвычайно сложно

$\qquad C_n=\sum \limits_{i=0}^{n-1}C_i C_{n-1-i}$
для $1000$ вполне хватит

[frankenstein]

ИСН в сообщении #939198 писал(а):

Есть быстрые методы нахождения чисел Каталана без деления, но они очень медленные.

Звучит противоречиво.