분수의 양 끝에서
다이아몬드 II의견: 0
양의 분수 \(\dfrac{p}{q}\) 와 양의 정수 \(N\)이 주어진다. 분모가 \(N\) 이하인 분수 중에서 \(\dfrac{p}{q}\) 에 가장 가까운 두 분수를 찾아야 한다.
구체적으로, 정수 \(a \ge 0\), \(1 \le b \le N\) 인 분수 \(\dfrac{a}{b}\) 들 가운데
-
\(\dfrac{a}{b} \le \dfrac{p}{q}\) 를 만족하면서 \(\dfrac{p}{q}\) 에 가장 가까운 (즉 가장 큰) 분수 (아래쪽 근사)
-
\(\dfrac{a}{b} \ge \dfrac{p}{q}\) 를 만족하면서 \(\dfrac{p}{q}\) 에 가장 가까운 (즉 가장 작은) 분수 (위쪽 근사)
를 각각 기약분수로 구하라. 두 조건을 만족하는 가장 가까운 분수가 여러 개라면 분모가 가장 작은 것을 택한다 (같은 값의 분수는 기약분수로 유일하다). 만약 \(\dfrac{p}{q}\) 자신을 분모 \(N\) 이하로 표현할 수 있다면 두 답은 모두 \(\dfrac{p}{q}\) 의 기약분수가 된다.
총 \(T\)개의 질의가 주어진다. \(p, q, N\)이 \(10^{18}\)에 달하므로 분모를 일일이 시도하는 방법으로는 풀 수 없다.
\(1 \le T \le 10^4\)
\(1 \le p \le 10^{18}\)
\(1 \le q \le 10^{18}\)
\(1 \le N \le 10^{18}\)
첫 줄에 질의의 수 \(T\)가 주어진다.
이어지는 \(T\)개의 줄에 각각 세 정수 \(p\), \(q\), \(N\)이 공백으로 구분되어 주어진다.
각 질의마다 한 줄에 네 정수 \(a_{\text{lo}}\), \(b_{\text{lo}}\), \(a_{\text{hi}}\), \(b_{\text{hi}}\) 를 공백으로 구분하여 출력한다. 앞의 두 수는 아래쪽 근사 \(\dfrac{a_{\text{lo}}}{b_{\text{lo}}}\), 뒤의 두 수는 위쪽 근사 \(\dfrac{a_{\text{hi}}}{b_{\text{hi}}}\) 이며 모두 기약분수이다.
2
22 7 5
3 2 10
3 1 16 5
3 2 3 2첫 질의 p/q=22/7≈3.142857, N=5. 분모 5 이하에서 22/7 이하로 가장 가까운 것은 3/1=3 (다른 후보 19/6 등은 분모>5). 22/7 이상으로 가장 가까운 것은 16/5=3.2. 따라서 3 1 16 5.
둘째 질의 p/q=3/2=1.5, N=10. 3/2은 분모 2≤10로 그대로 표현 가능하므로 아래·위 모두 3/2. 따라서 3 2 3 2.
2
5 1 1
1 3 2
5 1 5 1
0 1 1 2첫 질의 p/q=5/1=5, N=1. 분모 1로 5/1 그대로 표현되므로 5 1 5 1.
둘째 질의 p/q=⅓≈0.333, N=2. 분모 2 이하에서 ⅓ 이하 최댓값은 0/1=0, ⅓ 이상 최솟값은 ½=0.5. 따라서 0 1 1 2.
riseoj 작성
출처 Original
평가 및 의견
분수의 양 끝에서
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
분수의 양 끝에서