ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Алиса и Брандашмыг

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
— Отрубить ей голову! — завопила Королева во всю глотку.
Из общения с Красной королевой Алиса вынесла одну простую мысль — достаточно одного неудачного слова, и тебе отрубят голову. Поэтому Алиса начала шифровать разговоры со своим новым другом Брандашмыгом.
Не так давно ей удалось придумать достаточно простой в применении, но в то же время достаточно надёжный шифр. В качестве ключа Алиса берёт последовательность целых чисел x1, …, xn (0 ≤ xia − 1), где a — размер алфавита. Желая передать Брандашмыгу сообщение s = s1s2sr, она передаёт ему сообщение t = t1t2tr. При этом номер буквы t1 в алфавите — это номер буквы s1 плюс x1, номер буквы t2 — это номер буквы s2 плюс x2, и так далее (считая, что алфавит циклический, то есть после его последней буквы вновь идёт первая). После того как Алиса произносит первых n букв своего сообщения, она начинает использовать свою последовательность с начала — снова x1, затем x2
Алиса хочет знать, сколько различных ключей существует для её шифра. Алиса считает одинаковыми ключи, отличающиеся только циклическим сдвигом (например, [0, 1, 2, 0] и [2, 0, 0, 1]). Более того, Алиса боится, что её разговор могут подслушать, поэтому она не хочет использовать последовательности с периодом меньше n (которые могут быть представлены в виде более короткой последовательности, повторённой целое число раз, например, [0, 1, 0, 1]).

Исходные данные

В единственной строке записаны целые числа a и n (1 ≤ a ≤ 26; 1 ≤ n ≤ 10 000).

Результат

Выведите общее количество различных ключей для шифра, который придумала Алиса.

Примеры

исходные данныерезультат
3 4
18
10 2
45
Автор задачи: Павел Климов
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1857. Алиса и Брандашмыг