[python] 백준 1750 서로소의 개수

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

1750번: 서로소의 개수

 

 

문제 해결

• dp[i]를 최대공약수를 i로 가지는 경우의 수라고 정의하면 문제풀이는 끝이다.
• 미리 입력 값을 받아놓은다음 하나씩 돌아가며 dp[A[i]] += 1 해야한다.
• 각 입력값을 1부터 Maximum(입력값의 최댓값)까지 수 j를 돌면서 dp[(입력값과 j의 최대 공약수)] += dp[j]를 한다.

CODE

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

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