Неделимость биномиальных коэффициентов
Обозначим 
, где 0 ≤ i ≤ n и n, i - целые числа. Вам даны натуральное число n и простое число p. Требуется найти количество чисел i Є {0, 1, ..., n}, для которых Cin не делится на p.
Технические условия
Входные данные
В единственной строке входного файла заданы натуральное число n ≤ 1018 и простое число p < 1018.
Выходные данные
В единственную строку выходного файла выведите ответ на задачу.
Информация о задаче
Лимит времени: 0.5 секундыЛимит памяти: 64 MB
Баллы за пройденный тест: 1
Сложность: 43% 4/7
Автор: А.Лунев
Источник: Зимние сборы в Харькове 2010 День 1
Пример
Пример входных данныхSample 1 4 2 Sample 2 8 3 Sample 3 4 5 |
Пример выходных данныхSample 1 2 Sample 2 9 Sample 3 5 |
| ← Косточки для Шарика | Список задач | Иррациональные попарные расстояния → |