30510번 - 토마에 함수

미적분학 I 수업을 준비하기 위해 열심히 공부하던 세종이는 교재에서 새로운 함수를 하나 발견하였다. $0$ 이상 $1$ 이하의 실수 $x$에 대해 토마에 함수 $f(x)$는 $x$의 값에 따라 아래와 같은 대응 관계를 가진다.

• $x$가 무리수면 $f(x) =0$.
• $x=0$ 이면 $f(x) =1$.
• 이외의 경우 $x$를 기약분수 ${p\over q}\ (p,q$는 양의 정수, $q\neq 0)$ 꼴로 나타낼 수 있을 때 $f(x) ={1\over q}$.

임의의 유리수 $P\over Q$가 주어졌을 때, $f(x)\ge{P\over Q}$를 만족시키는 $0$ 이상 $1$ 이하의 실수 $x$의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 두 양의 정수 $P$, $Q$가 공백으로 구분되어 주어진다. $(1\le P\le Q\le 100\, 000)$

첫째 줄에 $f(x)\ge{P\over Q}$를 만족시키는 $0$ 이상 $1$ 이하의 실수 $x$의 개수를 출력한다.