Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CRCPOLY - Znajdź wielomian CRC

Załóżmy, że w pewnym protokole do danych jest dodawany kod CRC obliczany na podstawie wielomianu p(x), którego nie znasz. Masz dostęp do dwóch pakietów, będącymi ciągami binarnymi zawierającymi dane i kod CRC. Twoje zadanie polega na wyznaczeniu wielomianu maksymalnego stopnia, który mógł służyć do wyznaczania kodów CRC.

Inaczej mówiąc, masz dane dwa wielomiany w1 i w2 o współczynnikach z ciała Z2 i Twoje zadanie polega na wyznaczeniu wielomianu możliwie wysokiego stopnia, który dzieli w1 i w2 bez reszty.

Wejście

W pierwszym wierszu podana jest liczba testów. W kolejnych wierszach podane są poszczególne testy

Każdy test składa się z dwóch wierszy w których zapisane są oba pakiety. Pakiety zapisane są jako liczba szesnastkowa, reprezentująca ciąg binarny stanowiący pakiet. Długość tej liczby nie przekracza 500 cyfr.

Wyjście

Dla każdego testu, w osobnym wierszu należy podać szesnastkową reprezentację wyniku.

Przykład

Wejście:
5
5
3
5D7
489
C87
B6B
E23
6DB
E1B
A11


Wyjście:
3
AF
A9
2D
205


Dodane przez:Adam Nadolski
Data dodania:2007-03-08
Limit czasu wykonania programu:10.25s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.