Здравствуйте!
Помогите разобраться с алгоритмом.
Пытаюсь решить олимпиадную задачку по программированию,
вот тут обсуждение разных решений ;
задачу удалось свести к вычислению
, где
-- простое число.
Нашел по ссылке с википедии публикацию:
Andrew Granville, 1997, «Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers». Canadian Mathematical Society Conference Proceedings 20: 253-275. MR1483922.. В публикации рассматриваются два алгоритма, один -- "старый" (Davis and Webb), и усовершенствованный новый. Судя по асимптотическим оценкам, для моих целей вполне подходит "старый" алгоритм из той статьи. Соответствующая теорема приведена на 2-ой странице этой PDF-ки.
Места под теорему нет, см. следующий ответ (или pdf-ку).
Для того, чтобы разобраться с этим алгоритмом, я попытался вычислить
(равно
, кстати), и тут же столкнулся с неправильным результатом. Вот что получилось:
Разложим
по степеням
:
Вычислим
:
Теперь посчитаем (
обозначает произведение всех
без степеней
, т.е.
):
Подставляем значения:
Сокращаем:
Дальше считать не имеет смысла: значение в знаменателе значительно больше числителя, получается дробное число. А должно получиться
.
Помогите разобраться с этой теоремой и алгоритмом. Что я не так делаю?? В самой pdf-ке есть ссылка на Devis and Webb с доказательством, но я найти исходную статью не смог.
-- Вс апр 24, 2011 14:07:05 --Вот теорема:
Дана степень простого числа
и числа
.
Разложим
по степеням
:
, и пусть
--- наименьший положительный остаток (least positive residue) от
. Аналогично введем
. Пусть
--- количество индексов
, для которых
.
Тогда:
где
равно
, кроме случая
.
-- Вс апр 24, 2011 14:35:40 --Попробовал зайти с другой стороны, заменим знаменатель на числитель (найдем обратные элементы в кольце по модулю
):
Но всё равно не то, получается
. А должно быть
.
Не понимаю, где ошибка...