1
|
Задача 507. Пара рекуррентных последовательностейпостоянный адрес задачи: http://www.diofant.ru/problem/2423/показать код для вставки на свой сайт >> |
Задачу решили:
1
всего попыток:
1
поделиться задачей:
|
|
|
Задача опубликована:
06.05.13 08:00
Прислал:
admin
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
2
класс:
11 и старше
баллы: 100
Темы:
алгебра
|
|
|
Рассмотрим пару последовательностей an и s n , заданных следующим образом:
a1 = 1, s1 = 1, an = sn-1 mod n, sn = sn-1+ an×n.
(Здесь и далее "x mod y" означает остаток от деления x на y.)
Первые 10 элементов последовательности an:
1,1,0,3,0,3,5,4,1,9.
Первые 10 элементов последовательности sn:
1,3,3,15,15,33,68,100,109,199.
Обозначим через h(N,M) количество таких пар (p,q), для которых
1≤p≤q≤N и (sp + sp+1 +… + sq-1 + sq ) mod M = 0
Можно проверить, что h(10,10)=5, а соответствующие пары – (1,6), (4,5), (4,9), (6,9) и (8,8).
h(104,103)= 107796.
Найдите h(1012,106).
Пожалуйста, не пишите нам, что Вы не можете решить задачу.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Внимание! В обсуждении задачи запрещено публиковать ответы и давать подсказки.