Это почти прорыв!


На летнем этапе кубка SnarkNews Summer Series — 2008 я решил 2 задачи и почти решил третью! 😉

Хотелось бы поделиться некоторыми идеями, которые, конечно, далеко не новы, но мне приятно, что я до них додумался самостоятельно.

Лемма 1

Лемма:

Пусть A mod B = Y и C mod B = Z. Тогда A*C mod B = Y*Z mod B.

Доказательство:

Действительно, A = BQ + Y, C = BW + Z. A*C mod B = (BQ + Y)*(BW + Z) mod B = (B*B*Q*W + B*Q*Z + B*W*Y + Y*Z) mod B = Y*Z mod B.

Лемма 2

Лемма:

В последовательности A^n mod B есть цикл.

Доказательство:

Пусть A mod B = X_1, A^i mod B = X_i. Очевидно, что число различных значений X_i меньше, чем B, потому как мы имеем дело с остатками от деления, а они не могут превышать вечину делителя.

Пусть теперь для некоторого i существует k, такое что A^i mod B = A^k mod B, при этом i != k. Такая пара чисел существует ввиду конечной мощности множества остатков X_n. Докажем, что A^(i+1) mod B = A^(k+1) mod B.

A^(h+1) mod B = ( A^h * A ) mod B = {По лемме 1} = (A^h mod B) * (A mod B) mod B. Откуда следует что A^(i+1) mod B = A^(k+1) mod B.

Как это применяется для решения задач, я покажу в следующей своей публикации.

Реклама

Метки: , , , ,

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s


%d такие блоггеры, как: