백준 1750 서로소의 개수 파이썬

https://www.acmicpc.net/problem/1750

1750번: 서로소의 개수

배낭 문제로 풀리는걸 깨달으면 쉬운 문제이다. 수열의 원소를 선택해서 어떤 연산을 해서 나오는 경우의 수를 구할때, 배낭 문제를 사용하면 쉽게 풀 수 있다는걸 잊지 말자. 단, 연산의 교환법칙이 성립해야한다. 

import sys
import math
mod = 10000003
input = sys.stdin.readline

n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
SZ = max(a) + 1
dp = [0] * SZ
for i in range(n):
    for j in range(1, SZ):
        if dp[j]: dp[math.gcd(j, a[i])] += dp[j]
    dp[a[i]] += 1
print(dp[1] % mod)

코드는 간단하다.