32632번 - 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$의 최대공약수를 의미한다.

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