[백준/1750] 서로소의 개수 (Python)

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

1750번: 서로소의 개수

 

Difficulty : Gold 3

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

 

어떤 수열 S가 주어진다. 이때, 한 개 이상을 선택했을 때, 선택한 수의 최대공약수가 1이 되는 것의 개수를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에 수열의 각 원소 Si가 주어진다. 같은 수가 들어올 수도 있다. (1 ≤ N ≤ 50, 1 ≤ Si ≤ 100,000)

 

출력

 

첫째 줄에 정답을 10,000,003으로 나눈 나머지를 출력한다.

 

입력 예시

 

3
2
4
3

 

출력 예시

 

3

 

 

---

 

풀이

 

브루트포스로 해결하려면 최대 2^50의 경우의 수가 생기므로, 다른 방법을 모색해보아야 한다.

 

그런데, 셋 이상의 최대공약수 및 최소공배수 연산은 교환법칙 및 결합법칙 이 성립한다. 즉 1부터 n-1번째까지의 수의 대공약수와 n의 최대공약수는 1부터 n까지 전체의 최대공약수와 동일하다. 그렇다면, 겹치는 최대공약수 개수를 저장하여 이를 1부터 n까지 공약수 조합을 구해볼 수 있을 것이다.

 

dp[i][j]를 1부터 i까지의 수를 고려하였을 때 최대공약수가 j인 경우의 수라고 가정하자. i+1번째 수에 대해, 우리는 i+1번째 수를 사용하는 경우와 사용하지 않는 경우로 나눌 수 있다.

 

• 사용하는 경우 : j와 새로운 수 num[i+1]의 최대공약수를 gcd라고 둔다면, dp[i+1][gcd] += dp[i][j]가 성립한다.
• 사용하지 않는 경우 : 이 경우 i+1번째를 무시하고 최대공약수를 보존할 수 있으므로 dp[i+1][j] += dp[i][j]가 성립한다.
• 또한, 1부터 i까지의 수를 사용하지 않고 i+1번째 수만 사용하는 경우도 고려해야 한다. 이 때 dp[i+1][num[i+1]] += 1 이 성립한다.

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline
MOD = 10000003
def gcd(a, b) :
  while b > 0 :
    a, b = b, a % b
  return a

N = int(input())
num_list = [int(input()) for _ in range(N)]
count_one = lambda x : x.count(1)
dp = [defaultdict(int) for _ in range(N)]
dp[0][num_list[0]] = 1

for i in range(1, N) :
  for j in dp[i-1].keys() :
    val = gcd(num_list[i], j)
    dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD
    dp[i][val] = ( dp[i][val] + dp[i-1][j] ) % MOD
  dp[i][num_list[i]] += 1

print(dp[-1][1] % MOD)

풀이 완료!