문제
기약분수는 분자와 분모의 최대공약수가 1인 분수이다. 두 개의 분수가 주어질 때 두 분수 사이(주어진 두 개의 분수를 포함)에 존재하는 분수들 중에서 분모를 K로 하는 기약분수
는 몇 개가 있을까?
예를 들어 보자 두 개의 분수 1/2과 1/5사이에 분모를 20으로 하는 기약분수는 7/20과 9/20두개가 있다. 두 개의 분수가 주어질 때 두 분수 사이에 존재하는 분수들 중에서 분모를 K로 하는 기약분수를 구하는 프로그램을 작성하시오.
입력
첫 행에 첫 번째 분수의 분자 A와 분모 B, 두 번째 분수의 분자 C와 분모 D가 공백으로 구분되어 주어진다. 주어진 두개의
분수는 기약분수가 아닐 수도 있다. 네 수의 범위는 1 ≤ A < B ≤ 100,000 , 1 ≤ C < D ≤ 100,000 이다. 다음 행에 K (10≤K≤1,000,000)가 주어진다.
출력
하나의 행에 두 분수 사이에 분모를 K로 하는 기약분수의 개수를 출력하시오.
예제
1 2 1 5
20
2
출처
2010년 예선 초등3번
로그인해야 코드를 작성할 수 있어요.