시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 392 | 223 | 147 | 54.444% |
Given intervals [a, b] and [c, d], count the number of ordered pairs of co-prime integers (x, y) such that a ≤ x ≤ b and c ≤ y ≤ d. Coprime integers have no common factor greater than 1.
The input consists of a single line of four space-separated integers a, b, c, and d. These integers satisfy the bounds (1 ≤ a ≤ b ≤ 107, 1 ≤ c ≤ d ≤ 107).
Print a single integer: the number of coprime pairs (x, y) with a ≤ x ≤ b, c ≤ y ≤ d.
1 5 1 5
19
12 12 1 12
4
1 100 1 100
6087