시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 192 MB628597275623.427%

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

예제 입력 1

3
2 3 5
2
4 5

예제 출력 1

10

예제 입력 2

4
6 2 3 4
1
1

예제 출력 2

1

예제 입력 3

3
358572 83391967 82
3
50229961 1091444 8863

예제 출력 3

000012028
W3sicHJvYmxlbV9pZCI6IjI4MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YWNlOFx1ZDBkNVx1YmEzOVx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViOWU0XHVjNmIwIFx1ZDA3MCBBXHVjNjQwIEJcdWI5N2MgXHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWM2NDAgTVx1YWMxY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjOGZjXHVjNWM4XHVhY2UwLCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhY2YxXHVkNTU4XHViYTc0IEEsIE1cdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFjZjFcdWQ1NThcdWJhNzQgQlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgMSwwMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjZTAsIE5cdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNmMVx1ZDU1OFx1YmE3NCBBXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBNKDEgJmxlOyBNICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIxMzdcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgMSwwMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjZTAsIE1cdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNmMVx1ZDU1OFx1YmE3NCBCXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0NTAgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgOVx1Yzc5MFx1YjlhY1x1YmNmNFx1YjJlNCBcdWFlMzhcdWIyZTRcdWJhNzQsIFx1YjljOFx1YzljMFx1YjljOSA5XHVjNzkwXHViOWFjXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1Y2Q1Y1x1YjMwMCBcdWFjZjVcdWM1N2RcdWMyMThcdWFjMDAgMTAwMDAxMjAyOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMDAwMDEyMDI4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlpBREFcdTAxMDZBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgcmVjZWl2ZWQgYSBob21ld29yayBhc3NpZ25tZW50IHRvIGNvbXB1dGUgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIHRoZSB0d28gcG9zaXRpdmUgaW50ZWdlcnMgQSBhbmQgQi4gU2luY2UgdGhlIG51bWJlcnMgYXJlIHF1aXRlIGxhcmdlLCB0aGUgdGVhY2hlciBwcm92aWRlZCBoaW0gd2l0aCBOIHNtYWxsZXIgaW50ZWdlcnMgd2hvc2UgcHJvZHVjdCBpcyBBLCBhbmQgTSBpbnRlZ2VycyB3aXRoIHByb2R1Y3QgQi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gd291bGQgbGlrZSB0byB2ZXJpZnkgaGlzIHJlc3VsdCwgc28gaGUgaGFzIGFza2VkIHlvdSB0byB3cml0ZSBhIHByb2dyYW0gdG8gc29sdmUgaGlzIHByb2JsZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIHRoZSByZXN1bHQgaXMgbW9yZSB0aGFuIDkgZGlnaXRzIGxvbmcsIG91dHB1dCBvbmx5IHRoZSBsYXN0IDkgZGlnaXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiAxIDAwMCAwMDAgMDAwLCB3aG9zZSBwcm9kdWN0IGlzIHRoZSBudW1iZXIgQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTSAoMSAmbGU7IE0gJmxlOyAxMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvdXJ0aCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE0gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiAxIDAwMCAwMDAgMDAwLCB3aG9zZSBwcm9kdWN0IGlzIHRoZSBudW1iZXIgQi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiBudW1iZXJzIEEgYW5kIEIuIElmIHRoZSByZXN1bHQgaXMgbW9yZSB0aGFuIDkgZGlnaXRzIGxvbmcsIG91dHB1dCBvbmx5IHRoZSBsYXN0IChsZWFzdCBzaWduaWZpY2FudCkgOSBkaWdpdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZpcnN0IHNhbXBsZSBkZXNjcmlwdGlvbjogVGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIG51bWJlcnMgQSA9IDMwIGFuZCBCID0gMjAgZXF1YWxzIDEwLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 3번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: doju
  • 데이터를 추가한 사람: yuja