gcd와 최단 경로

$\newcommand{\dist}{\mathrm{dist}}$

1번 정점부터 $N$번 정점까지 총 $N$개의 정점으로 이루어진 그래프가 주어진다. 이 그래프는 다음과 같은 성질을 가진다.

$1 \leq x, y \leq N$을 만족하는 서로 다른 두 정수 $x, y$에 대하여,

• $\gcd(x, y) = 1$이면 $x$번 정점과 $y$번 정점을 잇는 간선이 존재한다.
• $\gcd(x, y) \neq 1$이면 $x$번 정점과 $y$번 정점을 잇는 간선은 존재하지 않는다.

$x$번 정점과 $y$번 정점을 잇는 최단 경로의 길이를 $\dist(x, y)$로 정의한다. 두 정점을 잇는 경로가 없다면 $\dist(x, y) = 10^{10^{10}}$으로 정의한다. 또한 정의에 따라 $\dist(x, x) = 0$이다.

$1$ 이상 $N$ 이하의 정수 $K$가 주어졌을 때, $\dist(x, K) = \gcd(x, K)$를 만족하는 $1$ 이상 $N$ 이하의 정수 $x$의 개수를 구한다.

첫째 줄에 정수 $K$와 $N$이 공백으로 구분되어 주어진다. ($1 \leq K \leq N \leq 10^6$)

첫째 줄에 조건을 만족하는 정수의 개수를 출력한다.

$\gcd(x, y)$는 $x$와 $y$의 최대공약수를 의미한다.

두 정점을 잇는 경로의 길이는 경로에 포함된 간선의 개수를 의미하며, 최단 경로의 길이는 그 중 최솟값을 의미한다.