0base42   8달 전

제출번호 : 103618032

 

입력:

10 -8 -5 6 1 4 8 6
9 -5 -3 6 7 3 9 6

정답 출력:

90 -122 -75 6 7 31 65 6
90 -22 -15 6 7 25 47 6
630 -39050 -5057 6 630 -14126 -4423 6
3732891016114524500 3266258479897895354 185792877260976195 6 8640475700 -9078860574 -2330526429 6

dlaud5379   7달 전

늦은 시간에 다소 두서 없이 댓글을 쓴 것 같아 다시 작성합니다.

해당 테스트 케이스에서 올바른 나눗셈 결과는 3732891016114524500 3266258479897895354 185792877260976195 6 8640475700 -9078860574 -2330526429 6이 아니라 8640475700 50258812842 430052427 6 8640475700 -9078860574 -2330526429 6이어야 한다고 생각합니다.

  • 나눗셈을 할 때 우변의 역수를 취하고 분모를 유리화($\frac{1}{a+b\sqrt{x}}$ = $\frac{a-b\sqrt{x}}{(a+b\sqrt{x})(a-b\sqrt{x})}$ = $\frac{a-b\sqrt{x}}{a^2-b^2x}$)하는 과정을 따라가면 상계를 넉넉하게 잡아도 100억 단위까지 나올 수 있고, 좌변의 분모까지 반영해도 1조 단위까지만 나올 수 있습니다. 제시하신 답의 373경은 분모로 등장하기에는 너무 큰 값입니다.
  • Wolfram|Alpha에서 계산한 결과가 제가 제시하고 있는 답과 일치합니다(실수 부분, 허수 부분. Alternate form 참조). Wolfram|Alpha를 사용하기 전에도 계산기의 도움을 받아 계산해서 같은 값을 얻었습니다.

맞은 사람 창에 있는 소스 중 최소 2개가 똑같이 3732891016114524500 3266258479897895354 185792877260976195 6 8640475700 -9078860574 -2330526429 6을 출력하고 있는 것을 보면 무언가가 있는 것 같긴 한데, 여건이 된다면 확인해 보겠습니다.

0base42   7달 전

제 코드는 나눗셈을 직접 전개한 코드입니다.

그래서 이 부분이 좀 의심스럽긴 합니다.

현재 위 제출 번호의 코드를 공개해 놓은 상태입니다.

+ 이 테스트 케이스는 testcase.ac에서 생성하였습니다.

입력:

10 -8 -5 6 1 4 8 6
9 -5 -3 6 7 3 9 6

오답 출력:

90 -122 -75 6 7 31 65 6
90 -22 -15 6 7 25 47 6
630 -39050 -5057 6 630 -14126 -4423 6
8640475700 50258812842 430052427 6 8640475700 -9078860574 -2330526429 6

정답 출력:

90 -122 -75 6 7 31 65 6
90 -22 -15 6 7 25 47 6
630 -39050 -5057 6 630 -14126 -4423 6
3732891016114524500 3266258479897895354 185792877260976195 6 8640475700 -9078860574 -2330526429 6

입력:

9 -4 8 10 8 -6 7 10
5 -9 1 10 7 -6 -9 10

오답 출력:

45 -101 49 10 56 -90 -23 10
45 61 31 10 56 6 121 10
1260 16613 -2398 10 840 -6676 -1609 10
22419707076 -7885773455 -1021608560 10 14946471384 11471998160 -1911528955 10

정답 출력:

45 -101 49 10 56 -90 -23 10
45 61 31 10 56 6 121 10
1260 16613 -2398 10 840 -6676 -1609 10
-128126604190396340 -140314865816505133 -18177908461535056 10 -9138535455679098472 7144412175655860560 -1190442201066455155 10

dlaud5379   7달 전

3732891016114524500 3266258479897895354 185792877260976195 6 8640475700 -9078860574 -2330526429 6을 출력하는 소스 중 37845788을 확인해 보았는데, 계산 과정에서 long long 오버플로우가 일어나는 것을 확인했습니다.

구체적으로는 계산 과정에 $\frac{881436402+307512387\sqrt{6}}{8640475700} + \frac{2468868822+6127002\sqrt{6}}{432023785}$이 등장하는데, 50줄에서 분자의 정수 부분인 r.b = x.b * y.a + x.a * y.b = 21,713,002,553,607,446,970(참값)이 오버플로우가 되어서 3,266,258,479,897,895,354이 됩니다. 마지막으로 올려주신 다음 케이스에서도 49줄에서 분모인 r.a = x.a * y.a = 13,962,312,927,045,679,716(참값)이 오버플로우되어서 문제에서 요구하는 $a_j > 0$ 조건을 만족하지 못하고 있습니다.

댓글을 작성하려면 로그인해야 합니다.