사용자 도구

사이트 도구


ps:problems:boj:9613

GCD 합

ps
링크acmicpc.net/…
출처BOJ
문제 번호9613
문제명GCD 합
레벨실버 3
분류

기초

시간복잡도O(t*n^2*logm)
인풋사이즈t<=100, n<=100, m<=1,000,000
사용한 언어Python
제출기록32972KB / 68ms
최고기록52ms
해결날짜2022/03/12

풀이

  • 그냥 모든 쌍에 대해서 GCD를 다 구해보는것으로 충분하다.
  • 시간복잡도는 O(n^2*logm)

코드

"""Solution code for "BOJ 9613. GCD 합".

- Problem link: https://www.acmicpc.net/problem/9613
- Solution link: http://www.teferi.net/ps/problems/boj/9613
"""

import itertools
import math


def main():
    t = int(input())
    for _ in range(t):
        # pylint: disable=unused-variable
        n, *nums = [int(x) for x in input().split()]
        print(sum(math.gcd(*t) for t in itertools.combinations(nums, 2)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N᠎ C O B H
 
ps/problems/boj/9613.txt · 마지막으로 수정됨: 2022/06/02 09:08 저자 teferi