문제
Q개의 독립적인 질의에 대해 다음 문제를 해결하세요.
네 정수 a, b, c, d (−10¹⁸ ≤ a, b, c, d ≤ 10¹⁸)가 주어집니다. 한 번의 연산에서, 다음 두 연산 중 하나를 수행할 수 있습니다:
연산 1: a에 b를 더합니다 (a += b).
연산 2: b에 a를 더합니다 (b += a).
목표는 (a, b)를 (c, d)로 변환하는 데 필요한 최소 연산 횟수를 구하는 것입니다. 만약 변환이 불가능하다면 −1을 출력하세요.
입력
첫 번째 줄에 정수 Q (1 ≤ Q ≤ 10⁵)가 주어집니다.
이후 Q개의 줄 각각에 네 정수 a, b, c, d가 공백으로 구분되어 주어집니다.
출력
각 질의에 대해 (a, b)를 (c, d)로 변환하기 위한 최소 연산 횟수를 한 줄에 하나씩 출력합니다. 만약 변환이 불가능하다면 −1을 출력하세요.
예제1
입력
4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3
출력
2
-1
3
0
첫 번째 질의: (5, −3)에서, 연산 1을 수행하면 (5 + (−3), −3) = (2, −3)이고, 다시 연산 1을 수행하면 (2 + (−3), −3) = (−1, −3). 총 2번의 연산으로 (−1, −3)로 변환됩니다.
두 번째 질의: (5, 3)를 (5, 2)로 변환하는 것은 불가능합니다.
세 번째 질의: (5, 3) → (5 + 3, 3) = (8, 3) → (8, 3 + 8) = (8, 11) → (8, 11 + 8) = (8, 19). 총 3번의 연산이 필요합니다.
네 번째 질의: (5, 3)는 이미 (5, 3)이므로 0번의 연산이 필요합니다.
출처
USACO 2025 February Platinum