시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2334 476 358 23.522%

문제

상근이는 학생들에게 두 양의 정수 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
W3sicHJvYmxlbV9pZCI6IjI4MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YWNlOFx1ZDBkNVx1YmEzOVx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViOWU0XHVjNmIwIFx1ZDA3MCBBXHVjNjQwIEJcdWI5N2MgXHVjOGZjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWM2NDAgTVx1YWMxY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjOGZjXHVjNWM4XHVhY2UwLCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVhY2YxXHVkNTU4XHViYTc0IEEsIE1cdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFjZjFcdWQ1NThcdWJhNzQgQlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4oMSAmbGU7IE4gJmxlOyAxMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWNlMCwgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2YxXHVkNTU4XHViYTc0IEFcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LigxICZsZTsgTSAmbGU7IDEwMDApIFx1YjEzN1x1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIDEsMDAwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhY2UwLCBNXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZjFcdWQ1NThcdWJhNzQgQlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDUwIFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIDlcdWM3OTBcdWI5YWNcdWJjZjRcdWIyZTQgXHVhZTM4XHViMmU0XHViYTc0LCBcdWI5YzhcdWM5YzBcdWI5YzkgOVx1Yzc5MFx1YjlhY1x1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWNkNWNcdWIzMDAgXHVhY2Y1XHVjNTdkXHVjMjE4XHVhYzAwIDEwMDAwMTIwMjhcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDAwMDAxMjAyOFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaQURBXHUwMTA2QSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIHJlY2VpdmVkIGEgaG9tZXdvcmsgYXNzaWdubWVudCB0byBjb21wdXRlIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiB0aGUgdHdvIHBvc2l0aXZlIGludGVnZXJzIEEgYW5kIEIuIFNpbmNlIHRoZSBudW1iZXJzIGFyZSBxdWl0ZSBsYXJnZSwgdGhlIHRlYWNoZXIgcHJvdmlkZWQgaGltIHdpdGggTiBzbWFsbGVyIGludGVnZXJzIHdob3NlIHByb2R1Y3QgaXMgQSwgYW5kIE0gaW50ZWdlcnMgd2l0aCBwcm9kdWN0IEIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIHdvdWxkIGxpa2UgdG8gdmVyaWZ5IGhpcyByZXN1bHQsIHNvIGhlIGhhcyBhc2tlZCB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIHNvbHZlIGhpcyBwcm9ibGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiB0aGUgcmVzdWx0IGlzIG1vcmUgdGhhbiA5IGRpZ2l0cyBsb25nLCBvdXRwdXQgb25seSB0aGUgbGFzdCA5IGRpZ2l0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMSAwMDAgMDAwIDAwMCwgd2hvc2UgcHJvZHVjdCBpcyB0aGUgbnVtYmVyIEEuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE0gKDEgJmxlOyBNICZsZTsgMTAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb3VydGggbGluZSBvZiBpbnB1dCBjb250YWlucyBNIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMSAwMDAgMDAwIDAwMCwgd2hvc2UgcHJvZHVjdCBpcyB0aGUgbnVtYmVyIEIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgbnVtYmVycyBBIGFuZCBCLiBJZiB0aGUgcmVzdWx0IGlzIG1vcmUgdGhhbiA5IGRpZ2l0cyBsb25nLCBvdXRwdXQgb25seSB0aGUgbGFzdCAobGVhc3Qgc2lnbmlmaWNhbnQpIDkgZGlnaXRzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: doju