28247번 - Nerd Sniping

문제

(출처: xkcd)

횡단보도를 건너던 물리학자는 이 문제를 해결하지 못했습니다! 여러분은 해결할 수 있을까요?

여러분이 해결해야 하는 문제는 다음과 같습니다.

저항값이 1ドル,円\Omega$인 이상적인 저항이 무한히 연결된 2차원 정사각 격자 회로가 있습니다. 이 격자에서 저항 4개가 연결된 한 점을 임의로 골라 그 점의 좌표를 $(0,0)$으로 정의합니다. 그리고, 그 점으로부터 저항이 연결된 방향을 따라 가로축과 세로축을 정하여 나머지 점들의 좌표를 정합니다. 예를 들어, $(0,0)$에서 오른쪽으로 저항 3ドル$개, 위쪽으로 저항 2ドル$개만큼 떨어진 점은 $(3,2)$로 표현합니다. 입력으로 어떤 정수 좌표 $(x,y)$가 주어졌을 때, 여러분은 $(0,0)$과 $(x,y)$ 사이의 등가 저항을 계산해야 합니다.

흥미롭게도, 이 문제의 정답은 모든 $(x,y)$에 대해 $\displaystyle \frac{s}{t}+\frac{2}{\pi} \frac{u}{v}$ ($\displaystyle \frac{s}{t}$와 $\displaystyle \frac{u}{v}$는 유리수)의 꼴로 유일하게 표현할 수 있음을 증명할 수 있습니다. 또한, 이 문제의 조건 하에서, 모든 정답에 대해 $at \equiv s \pmod{998244353}$이고 $bv \equiv u \pmod{998244353}$인 두 정수 0ドル \le a,b < 998244353$가 각각 유일하게 존재함이 보장됩니다. 여러분은 이러한 조건을 만족하는 두 정수 $a$와 $b$를 찾아 출력해야 합니다.

과연 여러분은 이 문제를 해결할 수 있을까요?

입력

첫 번째 줄에 테스트 케이스의 수 $T$가 주어집니다. (0ドル < T \le 10^5$)

두 번째 줄부터 $T+1$번째 줄까지 총 $T$개의 줄에 각각 두 정수 $x$와 $y$가 공백으로 분리되어 주어집니다. ($-2000 \le x,y \le 2000$)

출력

각 테스트 케이스에 대해 문제에서 설명한 대로 정답에 대응되는 두 정수 $a$와 $b$를 한 줄씩 공백으로 분리하여 출력하세요.

제한

노트

이 문제를 해결하기 위해서 필요한 물리적 지식 및 조건을 본 노트에 제시합니다.

• 회로 이론에서 사용하는 단위: $\text{V},ドル $\text{A},ドル $\Omega$는 각각 전압, 전류, 저항의 단위입니다. 본 노트의 나머지 부분에서 상수나 식 뒤에 해당 기호나 알파벳이 적혀 있다면, 별도의 언급이 없을 경우 해당 단위를 사용함을 의미합니다.
• 전압, 전위: 회로의 한 점에 $v ,円 \text{V}$의 전압을 가하고, 이 점과 전선으로 연결된 어떤 점을 접지(ground) 시켰다고 합시다. 이 경우 전압을 가한 지점에서의 전위가 $v ,円 \text{V},ドル 접지시킨 지점에서의 전위가 0ドル ,円 \text{V}$가 됩니다. 일반적으로 전지를 사용하는 경우 +극을 전압 공급원, -극을 접지라고 전제하고 설명하나, 엄밀히 설명하기 위해서는 전압 공급원과 접지를 두고 설명하는 것이 좋습니다.
• 전위차: 앞의 예시에서 전압을 가한 지점과 접지시킨 지점에서의 전위의 차이는 $v ,円 \text{V}$입니다. 이것을 두고 "두 지점 사이의 전위차가 $v ,円 \text{V}$이다"라고 합니다.

그림 1. 전압 공급원과 접지 간의 전위차가 5ドル ,円 \text{V}$인 경우의 회로도입니다.

• 저항, 전류: 전압 공급원과 접지 사이의 전위차가 $v ,円 \text{V}$이며 $r ,円 \Omega$의 저항이 있다면, 전압 공급원과 접지 사이의 전류는 옴의 법칙 $V=IR$에 따라 $(v/r) ,円 \text{A}$로 계산됩니다. 회로에서 저항은 지그재그 형태의 기호로 그려지며, 별도로 언급되지 않은 이상 저항이 아닌 전선에는 저항이 없다고 전제합니다.

그림 2. 전위차가 5ドル ,円 \text{V}$이고 저항이 2ドル,円 \Omega$인 경우, 전류는 $V/R = 5/2 ,円 \text{A}$로 계산됩니다.

• 직렬 연결: 세 점 $a,ドル $b,ドル $c$가 있어 $a$와 $b$를 연결하는 저항이 하나, $b$와 $c$를 연결하는 저항이 하나 있을 때의 경우에 $a$와 $c$ 사이 저항의 연결 형태를 두고 직렬 연결이라고 부릅니다. 두 저항 $R_1$과 $R_2$가 직렬 연결되면 두 저항의 합성 저항은 $R=R_1+R_2$에 의해 계산됩니다. 즉, 3ドル ,円 \Omega$의 저항과 2ドル ,円 \Omega$의 저항이 직렬 연결되면 합성 저항은 5ドル ,円 \Omega$가 됩니다.

그림 3. 직렬 연결의 예시입니다. 그림에서 $a$와 $c$ 사이 저항의 연결 형태를 두고 직렬 연결이라고 부릅니다.

• 병렬 연결: 두 점 $a,ドル $b$가 있어 $a$와 $b$를 연결하는 저항이 두 개 있을 경우에 $a$와 $b$ 사이 저항의 연결 형태를 두고 병렬 연결이라고 부릅니다. 두 저항 $R_1$과 $R_2$가 병렬 연결되면 두 저항의 합성 저항은 1ドル/R=1/R_1+1/R_2$에 의해 계산됩니다. 즉, 3ドル ,円 \Omega$의 저항과 2ドル ,円 \Omega$의 저항이 병렬 연결되면 합성 저항은 $\frac{1}{1/3+1/2}=6/5 ,円 \Omega$가 됩니다.

그림 4. 병렬 연결의 예시입니다. 그림에서 $a$와 $b$ 사이 저항의 연결 형태를 두고 병렬 연결이라고 부릅니다.

• 단순한 회로의 합성 저항: 직렬 연결과 병렬 연결로만 이루어진 단순한 회로 전체에서의 합성 저항은, 우선 병렬 연결된 저항들을 그에 대응되는 하나의 저항으로 치환시키고, 직렬 연결된 저항을 그에 대응되는 하나의 저항으로 다시 치환시키는 것을 반복함으로써 계산 가능합니다.

그림 5. 단순한 회로의 합성 저항을 계산하는 방법의 예시입니다.

• 키르히호프 전압 법칙: 하나의 폐회로 (그래프의 cycle과 같은 개념입니다.)에서 전위차의 합은 0ドル$입니다. 다시 말해서, 어떤 점에서 출발하여 하나의 사이클을 지나 출발한 점으로 돌아오면, 그 경로에서 지난 모든 전위차의 합은 0ドル$입니다. 이 때, 전류의 흐름과 반대 방향으로 지나는 경우에는 전위차를 음수로 취급함에 유의합니다.
• 키르히호프 전류 법칙: 하나의 정점을 기준으로 이동하는 전류의 합은 0ドル$입니다. 다시 말해서, 어떤 정점으로 들어오는 전류의 합과 나가는 전류의 합은 같습니다.
• 전류 분배 법칙: 여러 저항이 병렬로 연결되어 있을 경우에, 키르히호프 전압 법칙에 따라서 모든 저항 쌍에 걸리는 전위차는 동일해야 합니다. (각 저항 쌍이 하나의 폐회로를 이루기 때문입니다.) 또한, 옴의 법칙에 따라 전위차가 같을 때 각 저항에 흐르는 전류의 크기는 저항에 반비례하게 됩니다. 마지막으로, 키르히호프 전류 법칙에 따라서 각 저항으로 흐른 전류의 합은 전체 전류와 같아야 합니다. 이에 따라 각 저항에 흐르는 전류는 전체 저항에 따라 계산된 전류를 저항에 반비례하여 나누어 가진 값이 됩니다.

그림 6. 전류 분배 법칙이 실제로 병렬 연결된 저항 2개에 적용된 예시입니다.

• 전압 분배 법칙: 여러 저항이 직렬로 연결되어 있을 경우에, 키르히호프 전류 법칙에 따라서 각 저항에 흐르는 전류는 동일해야 합니다. (각 인접한 저항 사이의 정점에서 흐르는 전류의 합이 0ドル$이기 때문입니다.) 또한, 옴의 법칙에 따라 전류가 같을 때 각 저항에 흐르는 전압의 크기는 저항에 비례하게 됩니다. 이에 따라 각 저항에 흐르는 전류는 전체 저항에 따라 계산된 전위차를 저항에 비례하여 나누어 가진 값이 됩니다.

그림 7. 전압 분배 법칙이 실제로 직렬 연결된 저항 2개에 적용된 예시입니다.

• 등가 저항: 전압 구성원, 접지, 전선, 저항만으로 구성된 어떠한 회로의 일부분을 어떤 저항으로 바꾸었을 때 나머지 부분의 전위와 전류가 변하지 않는다면, 이에 해당하는 저항의 크기를 $r ,円 \Omega$라고 합시다. 이를 두고 "이 회로의 일부분의 등가 저항이 $r ,円 \Omega$이다"라고 합니다.

이제 여러분은 이 지식으로 어떤 유한한 회로에서 전압 공급원부터 접지된 지점까지의 등가 저항을 구할 수 있습니다! 유한한 회로에 대한 등가 저항의 계산은 이 문제에서 직접 연습해 볼 수 있습니다.

하지만, 이 문제는 유한한 회로를 다루지 않습니다! 이러한 이유로, 위에서 주어진 조건만으로는 지문에서 주어진 회로를 완전히 분석할 수 없습니다. 따라서 본 노트에 유한한 회로를 통해 본 문제를 정의하는 방법을 설명합니다.

• $C_n$을 문제에서 주어진 회로와 전반적인 모양은 같으나, 중심이 $(0,0)$이고 한 변의 저항 개수가 2ドルn$개인 유한한 정사각 격자 회로로 정의합시다.
• $R_n(x,y)$를 $C_n$ ($n \ge |x|,ドル $n \ge |y|$)에서 $(0,0)$과 $(x,y)$ 사이의 등가 저항으로 정의합시다.
• $n$이 무한대로 발산할 때, 등가 저항 $\displaystyle \lim _{n \to \infty} R_n(x,y)$는 위 지문에서 설명한 조건을 만족하는 어떤 값 $R$로 수렴합니다.
• 여러분은 이 값 $R$에 따라 지문에 주어진 대로 해당하는 두 정수 $a,ドル $b$를 출력하면 됩니다.