시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB37219115252.234%

문제

집합 S = {x1, x2, ..., xn}가 인수에 대해서 닫혀있으려면, 모든 xi ∈ S에 대해서, xi의 모든 약수 d는 d ∈ S를 만족해야 한다.

인수에 대해 닫힌 집합 S를 최대공약수 행렬 (S) = (sij), sij = GCD(xi,xj)로 만든 뒤, 이 행렬의 행렬식 (determinant)를 구하는 프로그램을 작성하시오.

\(D_n = \begin{vmatrix}  \text{gcd}\left(x_1,x_1\right) & \text{gcd}\left(x_1,x_2\right) & \text{gcd}\left(x_1,x_3\right) & \dots & \text{gcd}\left(x_1,x_n\right) \\ \text{gcd}\left(x_2,x_1\right) & \text{gcd}\left(x_2,x_2\right) & \text{gcd}\left(x_2,x_3\right) & \dots & \text{gcd}\left(x_2,x_n\right) \\ \text{gcd}\left(x_3,x_1\right) & \text{gcd}\left(x_3,x_2\right) & \text{gcd}\left(x_3,x_3\right) & \dots & \text{gcd}\left(x_3,x_n\right) \\ \dots & \dots & \dots & \dots & \dots \\ \text{gcd}\left(x_n,x_1\right) & \text{gcd}\left(x_n,x_2\right) & \text{gcd}\left(x_n,x_3\right) & \dots & \text{gcd}\left(x_n,x_n\right) \\ \end{vmatrix}\)

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 집합 S의 원소 개수 n(0 < n < 1,000)이 주어진다. 

다음 줄에는 집합의 원소 x1, x2, ..., xn이 주어진다. (0 < xi < 2*109, xi는 정수)

출력

각 테스트 케이스에 대해서 입력으로 주어진 집합 S의 최대공약수 행렬식을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
2
1 2
3
1 3 9
4
1 2 3 6

예제 출력 1

1
12
4
W3sicHJvYmxlbV9pZCI6IjM3NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTggXHVkNTg5XHViODJjXHVjMmRkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5ZDFcdWQ1NjkgUyA9IHt4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+bjxcL3N1Yj59XHVhYzAwIFx1Yzc3OFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViMmViXHVkNjAwXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWJhYThcdWI0ZTAgeDxzdWI+aTxcL3N1Yj4gJmlzaW47IFNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCB4PHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNTdkXHVjMjE4IGRcdWIyOTQgZCAmaXNpbjsgU1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzhcdWMyMThcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjJlYlx1ZDc4YyBcdWM5ZDFcdWQ1NjkgU1x1Yjk3YyBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTggXHVkNTg5XHViODJjIChTKSA9IChzPHN1Yj5pajxcL3N1Yj4pLCBzPHN1Yj5pajxcL3N1Yj4gPSBHQ0QoeDxzdWI+aTxcL3N1Yj4seDxzdWI+ajxcL3N1Yj4pXHViODVjIFx1YjljY1x1YjRlMCBcdWI0YTQsIFx1Yzc3NCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkNTg5XHViODJjXHVjMmRkIChkZXRlcm1pbmFudClcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxcKERfbiA9IFxcYmVnaW57dm1hdHJpeH0gJm5ic3A7XFx0ZXh0e2djZH1cXGxlZnQoeF8xLHhfMVxccmlnaHQpICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMSx4XzJcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzEseF8zXFxyaWdodCkgJmFtcDsgXFxkb3RzICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMSx4X25cXHJpZ2h0KSBcXFxcIFxcdGV4dHtnY2R9XFxsZWZ0KHhfMix4XzFcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzIseF8yXFxyaWdodCkgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8yLHhfM1xccmlnaHQpICZhbXA7IFxcZG90cyAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzIseF9uXFxyaWdodCkgXFxcXCBcXHRleHR7Z2NkfVxcbGVmdCh4XzMseF8xXFxyaWdodCkgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8zLHhfMlxccmlnaHQpICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMyx4XzNcXHJpZ2h0KSAmYW1wOyBcXGRvdHMgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8zLHhfblxccmlnaHQpIFxcXFwgXFxkb3RzICZhbXA7IFxcZG90cyAmYW1wOyBcXGRvdHMgJmFtcDsgXFxkb3RzICZhbXA7IFxcZG90cyBcXFxcIFxcdGV4dHtnY2R9XFxsZWZ0KHhfbix4XzFcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4X24seF8yXFxyaWdodCkgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF9uLHhfM1xccmlnaHQpICZhbXA7IFxcZG90cyAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4X24seF9uXFxyaWdodCkgXFxcXCBcXGVuZHt2bWF0cml4fVxcKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWQ1NjkgU1x1Yzc1OCBcdWM2ZDBcdWMxOGMgXHVhYzFjXHVjMjE4IG4oMCAmbHQ7IG4gJmx0OyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWM2ZDBcdWMxOGMgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPm48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmx0OyB4PHN1Yj5pPFwvc3ViPiAmbHQ7IDIqMTA8c3VwPjk8XC9zdXA+LCB4PHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWM4MTVcdWMyMTgpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjOWQxXHVkNTY5IFNcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4IFx1ZDU4OVx1YjgyY1x1YzJkZFx1Yzc0NCAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM3NTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHQ0QgRGV0ZXJtaW5hbnQiLCJkZXNjcmlwdGlvbiI6IjxwPldlIHNheSB0aGF0IGEgc2V0IFMgPSB7eDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPm48XC9zdWI+fSBpcyBmYWN0b3IgY2xvc2VkIGlmIGZvciBhbnkgeGkgJmlzaW47IFMgYW5kIGFueSBkaXZpc29yIGQgb2YgeGkgd2UgaGF2ZSBkICZpc2luOyBTLiBMZXQmcnNxdW87cyBidWlsZCBhIEdDRCBtYXRyaXggKFMpID0gJm5ic3A7KHM8c3ViPmlqPFwvc3ViPiksIHdoZXJlIHM8c3ViPmlqPFwvc3ViPiZuYnNwOz0gR0NEKHg8c3ViPmk8XC9zdWI+LHg8c3ViPmo8XC9zdWI+KSZuYnNwOyZuZGFzaDsgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIHg8c3ViPmk8XC9zdWI+IGFuZCB4PHN1Yj5qPFwvc3ViPi4gR2l2ZW4gdGhlIGZhY3RvciBjbG9zZWQgc2V0IFMsIGZpbmQgdGhlIHZhbHVlIG9mIHRoZSBkZXRlcm1pbmFudDombmJzcDs8XC9wPlxyXG5cclxuPHA+XFwoRF9uID0gXFxiZWdpbnt2bWF0cml4fSAmbmJzcDtcXHRleHR7Z2NkfVxcbGVmdCh4XzEseF8xXFxyaWdodCkgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8xLHhfMlxccmlnaHQpICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMSx4XzNcXHJpZ2h0KSAmYW1wOyBcXGRvdHMgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8xLHhfblxccmlnaHQpIFxcXFwgXFx0ZXh0e2djZH1cXGxlZnQoeF8yLHhfMVxccmlnaHQpICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMix4XzJcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzIseF8zXFxyaWdodCkgJmFtcDsgXFxkb3RzICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfMix4X25cXHJpZ2h0KSBcXFxcIFxcdGV4dHtnY2R9XFxsZWZ0KHhfMyx4XzFcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzMseF8yXFxyaWdodCkgJmFtcDsgXFx0ZXh0e2djZH1cXGxlZnQoeF8zLHhfM1xccmlnaHQpICZhbXA7IFxcZG90cyAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4XzMseF9uXFxyaWdodCkgXFxcXCBcXGRvdHMgJmFtcDsgXFxkb3RzICZhbXA7IFxcZG90cyAmYW1wOyBcXGRvdHMgJmFtcDsgXFxkb3RzIFxcXFwgXFx0ZXh0e2djZH1cXGxlZnQoeF9uLHhfMVxccmlnaHQpICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfbix4XzJcXHJpZ2h0KSAmYW1wOyBcXHRleHR7Z2NkfVxcbGVmdCh4X24seF8zXFxyaWdodCkgJmFtcDsgXFxkb3RzICZhbXA7IFxcdGV4dHtnY2R9XFxsZWZ0KHhfbix4X25cXHJpZ2h0KSBcXFxcIFxcZW5ke3ZtYXRyaXh9XFwpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4gKDAgJmx0OyBuICZsdDsgMTAwMCksIHRoYXQgc3RhbmRzIGZvciB0aGUgY2FyZGluYWxpdHkgb2YgUy4gVGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgbnVtYmVycyBvZiBTOiB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7LCB4PHN1Yj5uPFwvc3ViPi4gSXQgaXMga25vd24gdGhhdCBlYWNoIHhpIGlzIGFuIGludGVnZXIsIDAgJmx0OyB4PHN1Yj5pPFwvc3ViPiAmbHQ7IDIqMTA8c3VwPjk8XC9zdXA+LiBUaGUgaW5wdXQgZGF0YSBzZXQgaXMgY29ycmVjdCBhbmQgZW5kcyB3aXRoIGFuIGVuZCBvZiBmaWxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBmaW5kIGFuZCBwcmludCB0aGUgdmFsdWUgRDxzdWI+bjxcL3N1Yj4gbW9kIDEwMDAwMDAwMDcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2008 H번