레이팅 미적용영리한 소 베시는 새로운 흥밋거리, 수학 마법을 발견했다! 어느 날 농부 존의 목장 들판을 거닐던 베시는 마법이 깃든 건초 더미 두 개를 우연히 발견한다. 첫 번째 더미에는 건초 \(a\)뭉치, 두 번째 더미에는 \(b\)뭉치가 있다(\(1\le a,b\le 10^{18}\)).
건초 옆 흙 속에 반쯤 파묻힌 고대 두루마리를 발견한다. 두루마리를 펼치자 빛나는 글자들이 예언을 드러낸다.
위대한 초원의 명을 이루려면, 선택받은 자는 이 소박한 두 건초 더미를 정확히 \(c\)뭉치와 \(d\)뭉치로 만들어야 한다. 더도 말고 덜도 말고.
베시는 자신이 다음 두 가지 주문만 사용할 수 있음을 깨닫는다.
- 마법으로 새 건초를 만들어 첫 번째 더미의 크기를 현재 두 번째 더미에 있는 양만큼 늘릴 수 있다.
- 마법으로 새 건초를 만들어 두 번째 더미의 크기를 현재 첫 번째 더미에 있는 양만큼 늘릴 수 있다.
이 연산들은 순차적으로 수행해야 하지만, 횟수와 순서에는 제한이 없다. 첫 번째 더미가 정확히 \(c\)뭉치, 두 번째 더미가 정확히 \(d\)뭉치가 되어야 한다(\(1\le c,d\le 10^{18}\)).
\(T\)개(\(1\le T\le 10^4\))의 독립적인 테스트 케이스 각각에 대해, 예언을 이루는 데 필요한 연산의 최소 횟수를 출력하고, 불가능하다면 -1을 출력하시오.
Problem credits: Benjamin Qi
배점
- 입력 3-4: \(\max(c, d) \le 20 \cdot\min(a, b)\)
- 입력 5-7: \(T \le 10\)이고 \(a,b,c,d\le 10^6\)
- 입력 8-12: 추가 제약이 없다
Problem credits: Benjamin Qi
첫째 줄에 \(T\)가 주어진다.
다음 \(T\)개의 줄에 각각 네 정수 \(a,b,c,d\)가 주어진다.
각 테스트 케이스의 답을 \(T\)개의 줄에 출력한다.
4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3-1
3
-1
0In the first test case, it is impossible since \(b>d\) initially, but operations
can only increase \(b\).
In the second test case, initially the two piles have \((5, 3)\) bales. Bessie
can first increase the first pile by the amount in the second pile, resulting in
\((8, 3)\) bales. Bessie can then increase the second pile by the new amount in
the first pile, and do this operation twice, resulting in \((8, 11)\) and finally
\((8, 19)\) bales. This matches \(c\) and \(d\) and is the minimum number of
operations to get there.
Note that the third test case has a different answer than the second because \(c\)
and \(d\) are swapped (the order of the piles matters).
In the fourth test case, no operations are necessary.
1
1 1 1 1000000000000000000999999999999999999riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Silver