서로소 격자점 세기
다이아몬드 IV의견: 0
두 닫힌 구간 \([a, b]\)와 \([c, d]\)가 주어진다. \(a \le i \le b\)이고 \(c \le j \le d\)이며 \(\gcd(i, j) = 1\)을 만족하는 정수 순서쌍 \((i, j)\)의 개수를 구하여라.
여러 개의 질의가 주어지며, 각 질의마다 위 개수를 답해야 한다. 범위가 매우 크므로 모든 쌍을 직접 확인하는 풀이는 통과할 수 없다.
\(1 \le Q \le 50{,}000\)
\(1 \le a \le b \le 10^6\)
\(1 \le c \le d \le 10^6\)
첫 줄에 질의의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 네 정수 \(a\), \(b\), \(c\), \(d\)가 주어진다.
각 질의에 대해 조건을 만족하는 순서쌍의 개수를 한 줄에 하나씩 출력한다.
2
1 3 1 3
2 4 6 9
7
6첫 질의: \(i,j \in [1,3]\)인 9쌍 중 gcd가 1인 것은 (1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)로 7쌍이다 (단 (2,2),(3,3)은 제외). 둘째 질의: \(i \in [2,4]\), \(j \in [6,9]\) 중 서로소인 쌍은 6쌍이다.
2
1 1 1 1
10 10 5 5
1
0\((1,1)\)은 gcd가 1이므로 1. \((10,5)\)는 gcd가 5이므로 0.
riseoj 작성
출처 Original
평가 및 의견
서로소 격자점 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
서로소 격자점 세기