서로소 정수
시간 제한2초메모리 제한512 MB
a 이상 b 이하의 x와 c 이상 d 이하의 y 중에서 최대공약수가 1인 순서쌍 (x, y)의 개수를 센다.
문제
구간 [a, b]와 [c, d]가 주어진다. a ≤ x ≤ b, c ≤ y ≤ d이면서 서로소인 정수 순서쌍 (x, y)의 개수를 구하라. 서로소인 두 정수는 1보다 큰 공약수를 갖지 않는다.
입력
입력은 한 줄로 주어지며, 공백으로 구분된 네 정수 a, b, c, d가 들어온다. 이 정수들은 다음 조건을 만족한다. (1 ≤ a ≤ b ≤ 107, 1 ≤ c ≤ d ≤ 107)
출력
a ≤ x ≤ b, c ≤ y ≤ d인 서로소 순서쌍 (x, y)의 개수를 정수 하나로 출력하라.