CS
Задачник Базовый курс EN

Задача

Год по индикту

теория чисел предподсчёт

Старые грамоты и хроники нередко датировали не только годом, но и номерами в трёх календарных циклах: индиктом — номером года в пятнадцатилетнем цикле, золотым числом — номером в девятнадцатилетнем лунном цикле, и солнечным кругом — номером в двадцативосьмилетнем цикле, после которого дни недели в юлианском календаре повторяются на тех же числах. В 1583 году Иосиф Скалигер заметил, что три номера вместе повторяются только через 15 · 19 · 28 = 7980 лет, и назвал такой промежуток юлианским периодом. Его первый год, 4713 год до н. э., — тот, где все три номера равны единице.

Для года Y нашей эры индикт равен (Y + 2) mod 15 + 1, золотое число — Y mod 19 + 1, солнечный круг — (Y + 8) mod 28 + 1. В 2026 году это 4, 13 и 19. Архивисту нужно обратное: по трём номерам найти год. Годы считаются от 4713 года до н. э. до 3267 года н. э. включительно; нулевого года нет — за 1 годом до н. э. сразу идёт 1 год н. э.

Вход

В первой строке число запросов t (1 ≤ t ≤ 100 000). В каждой из следующих строк — индикт i, золотое число g и солнечный круг s (1 ≤ i ≤ 15, 1 ≤ g ≤ 19, 1 ≤ s ≤ 28).

Выход

Для каждого запроса — год в виде N AD для нашей эры или N BC до нашей эры, например 2026 AD или 45 BC.

Примеры

Пример 1

Вход
3
4 13 19
11 7 24
4 2 10
Выход
2026 AD
1583 AD
1 AD

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
5 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Номер года в юлианском периоде x (от 1 до 7980) даёт остатки x mod 15, x mod 19, x mod 28, совпадающие с номерами циклов, если номер 15 считать остатком 0, номер 19 — нулём и так далее. Модули 15, 19, 28 попарно взаимно просты. Что гарантирует китайская теорема?

2Подсказка 2

Год периода 4714 — это 1 год н. э. Какой год периода соответствует 1 году до н. э.? А 45 году до н. э.?

3Идея

По китайской теореме об остатках тройка остатков задаёт номер года периода однозначно. Найти его можно алгоритмом Гарнера: x = c₀ + 15c₁ + 285c₂, где c₀ = i mod 15, c₁ = (g − c₀)·15⁻¹ mod 19, c₂ = ((s − c₀)·15⁻¹ − c₁)·19⁻¹ mod 28. Или формулой де Бийи: x = (6916i + 4200g + 4845s) mod 7980. А можно и заранее заполнить таблицу из всех 7980 лет — их всего столько.

4Разбор

Находим номер x от 1 до 7980; остаток 0 означает год 7980, то есть 3267 год н. э. Дальше перевод в эру: если x > 4713, это год x − 4713 н. э.; иначе — год 4714 − x до н. э. Проверка на краях: x = 4714 → 1 AD, x = 4713 → 1 BC, x = 1 → 4713 BC.

Откуда 4714 и 4713. Астрономы нумеруют годы подряд: 1 год до н. э. у них — год 0, 2 год до н. э. — год −1. В этом счёте год периода x — это астрономический год x − 4713, и историческая запись получается из него так: положительный номер — тот же год н. э., ноль и отрицательные — год 1 − (x − 4713) = 4714 − x до н. э.

4+Решение
5Сложность

O(1) на запрос: несколько умножений по модулям 15, 19, 28. С таблицей — O(1) на запрос и 7980 записей заранее.

6Типичные ошибки
  • Год ноль. Формула 4713 − x для лет до н. э. ошибается на единицу: 1 год до н. э. выйдет «0 BC». Нулевого года в исторической нумерации нет.
  • Номер 15 вместо остатка 0. Номера циклов идут от 1 до 15, а остатки — от 0 до 14. Если подставить в формулу Гарнера 15 как есть, ответ не изменится только потому, что 15 ≡ 0 по модулю 15; с вычитанием же легко получить отрицательное число, а в Go % от отрицательного числа отрицателен.
  • Год 7980. Остаток 0 по модулю 7980 — это не год 0 периода, а последний, 7980-й год: 3267 год н. э.

Алгоритмы задачи

NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи
Каталог алгоритмов