시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4923 1471 1238 37.675%

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력 1

70
3
35
W3sicHJvYmxlbV9pZCI6Ijk2MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJHQ0QgXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NTggR0NEXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMSAmbGU7IHQgJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwO1x1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMTggbiAoMSAmbHQ7IG4gJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgMTAwMDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjMzBkXHVjNzU4IEdDRFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk2MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdW0gb2YgR0NEIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBuIHBvc2l0aXZlIGludGVnZXJzLCB5b3UgaGF2ZSB0byBmaW5kIHRoZSBzdW1tYXRpb24gb2YgR0NEIChncmVhdGVzdCBjb21tb24gZGl2aXNvcikgb2YgZXZlcnkgcG9zc2libGUgcGFpciBvZiB0aGVzZSBpbnRlZ2Vycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGlzIGFuIGludGVnZXIgbiAoMSZsdDsgbiAmbHQ7MTAwKSB0aGF0IGRldGVybWluZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGUgZm9sbG93aW5nIG4gbGluZXMgYXJlIHRoZSBuIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIDIgcGFydHM6IGZpcnN0IHBhcnQgaXMgdGhlIG51bWJlciBtICgxJmx0OyBtICZsdDsxMDApIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBpbnB1dCBpbnRlZ2Vycywgc2Vjb25kIHBhcnQgaW5jbHVkZXMgbSBwb3NpdGl2ZSBpbnRlZ2Vycy4gVGhlIGlucHV0IGludGVnZXJzIGRvIG5vdCBleGNlZWQgMTAwMDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHNob3cgdGhlIHN1bW1hdGlvbiBvZiBHQ0RzIG9mIGV2ZXJ5IHBvc3NpYmxlIHBhaXIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Thailand > 2013 ACM-ICPC Asia Phuket Regional Programming Contest PE번

  • 어색한 표현을 찾은 사람: alkyne
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: bessapple14
  • 잘못된 데이터를 찾은 사람: tncks0121
  • 데이터를 추가한 사람: topology