Взаимно простые номера в журнале
Условие
В школе у учителя есть число M — «номер темы». Он смотрит на номера учеников в журнале от 1 до N и хочет посчитать, для скольких номеров выполняется условие:
- у номера ученика и числа M нет общего делителя больше 1.
Такие числа называют взаимно простыми.
Напечатайте, сколько чисел x от 1 до N (включая границы) взаимно просты с M.
Формат ввода
Одна строка: два целых числа N и M.
Формат вывода
Одно целое число — ответ.
Ограничения
- 1 ≤ N ≤ 10^12
- 1 ≤ M ≤ 10^6
- Значения могут не помещаться в 32-битный тип, используйте 64-битные целые (в Python это не проблема).
Пример
Ввод:
10 12Вывод:
3Решить задачу с автопроверкой на Python →
Куда дальше
- Python на олимпиадах — где языка хватает с запасом, а где начинают значить лимиты — с замерами
- На программиста по олимпиаде: путь по классам — что даёт диплом, куда с ним берут на ИТ-направления и почему решает 9 класс
- Вердикты судьи: WA, TLE, RE, PE, CE — что значит каждый код проверяющей системы и где искать причину