백준 온라인 저지, 구현 / 9613번: GCD합 (파이썬 / 백준 실버문제)

문제 주소: https://www.acmicpc.net/problem/9613

문제

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

입력

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

출력

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

제한

예제 입력 1

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

예제 출력 1

70
3
35

힌트

W3sicHJvYmxlbV9pZCI6Ijk2MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJHQ0QgXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NTggR0NEXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMSAmbGU7IHQgJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwO1x1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMTggbiAoMSAmbHQ7IG4gJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMThcdWIyOTQgMSwwMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NTggR0NEXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTYxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1bSBvZiBHQ0QiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIG4gcG9zaXRpdmUgaW50ZWdlcnMsIHlvdSBoYXZlIHRvIGZpbmQgdGhlIHN1bW1hdGlvbiBvZiBHQ0QgKGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yKSBvZiBldmVyeSBwb3NzaWJsZSBwYWlyIG9mIHRoZXNlIGludGVnZXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYW4gaW50ZWdlciBuICgxJmx0OyBuICZsdDsxMDApIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBhcmUgdGhlIG4gdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgMiBwYXJ0czogZmlyc3QgcGFydCBpcyB0aGUgbnVtYmVyIG0gKDEmbHQ7IG0gJmx0OzEwMCkgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGlucHV0IGludGVnZXJzLCBzZWNvbmQgcGFydCBpbmNsdWRlcyBtIHBvc2l0aXZlIGludGVnZXJzLiBUaGUgaW5wdXQgaW50ZWdlcnMgZG8gbm90IGV4Y2VlZCAxMDAwMDAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgc2hvdyB0aGUgc3VtbWF0aW9uIG9mIEdDRHMgb2YgZXZlcnkgcG9zc2libGUgcGFpci4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 가능한 모든 경우의 수에 대해 GCD 합을 구해 출력한다.

코드

# https://www.acmicpc.net/problem/9613
# 접근 방법
# 가능한 모든 경우의 수에 대해 GCD 합을 구해 출력한다.
def gcd(a, b):
    if a % b:
        return gcd(b, a%b)
    return b

t = int(input())
for _ in range(t):
    arr = list(map(int, input().split()))
    result = 0
    for i in range(1, arr[0]+1):
        for j in range(i+1, arr[0]+1):
            result += gcd(max(arr[i], arr[j]), min(arr[i], arr[j]))
    print(result)