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

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

Ограничение времени: 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