[백준 14476번] 최대공약수 하나 빼기 (Python3)

import sys
input = sys.stdin.readline
from math import sqrt

def check(x):
  cnt = 0
  idx = 0
  for i in range(N):
    if nums[i]%x:
      cnt += 1
      idx = i
      if cnt > 1:
        return 2,0
  return cnt,idx

def divide(x,idx):
  for i in range(N):
    if i == idx:
      continue
    nums[i] //= x

N = int(input())
data = [*map(int,input().split())]
nums = data[:]
nums.sort()

MIN = nums[1]
sq = int(sqrt(MIN))
sqsq = int(sqrt(sq))

prime = []
visited = [0]*(sq+1)
for p in range(2,sq+1):
  if visited[p]:
    continue
  prime.append(p)
  if p>sqsq:
    continue
  i = 2
  while p*i<=sq:
    visited[p*i] = 1
    i+=1

gcd = 1
gcdlist = [1]*N

for p in prime:
  while True:
    cnt,idx = check(p)
    if cnt == 2:
      break
    if cnt == 1:
      gcdlist[idx] *= p
      divide(p,idx)
    else:
      gcd *= p
      divide(p,-1)
for i in range(2):
  if data[i] == nums[i]:
    p = nums[i]
    cnt,idx = check(p)
    if cnt == 1:
      gcdlist[idx] *= p
    elif cnt == 0:
      gcd *= p
mgcd = max(gcdlist)
if mgcd == 1:
  print(-1)
else:
  print(gcd*mgcd,data[gcdlist.index(mgcd)])

무식하게 풀었는데 맞았다.

 

일단 내 알고리즘을 설명하면,

1. 유클리드 호제법으로 소수를 구해준다.

2. 모든 소수에 대해서 소인수분해를 진행한다. 이때 나누어떨어지지 않는 수가 2개 이상이면 continue하고, 1개면 gcdlist에 나누어지지 않는 숫자의 인덱스에 저장, 0개면 최대공약수(모든 숫자들의)를 갱신한다.

3. gcdlist의 가장 큰 값과 최대공약수의 곱을 결과로 출력, 이때 가장 큰 값의 숫자도 출력한다.

 

여기서 시간 단축을 위해서,

1. 유클리드 호제법으로 소수를 구할 때, 두번째로 작은 수의 루트값보다 작은 소수를 구한다.

(소수가 아닌 경우 약수의 최댓값이 루트이기 때문 + 두번째인 이유는 첫번째 숫자를 제외해야 할 수도 있기 때문)

2. 소수일 수 있으므로 가장 작은 수와 두번째로 작은 수에 대해서 소인수분해를 해주어야한다.

(두번째까지 하는 이유는 위와 같이 첫번째 숫자를 제외해야 할 수도 있기 때문)

 

 

아이디어는 사실 금방 떠올렸지만 시간복잡도상 안되는 풀이라고 생각했는데, 제출해보니 넉넉하게 통과되었다.

다만 이 문제는 원래 누적합 개념을 응용한 누적최대공약수를 이용해서 푸는 문제라고 한다.

누적최대공약수라니, 생각지도 못한 방법이다.

 

 

오늘의 교훈) 누적합 개념을 여러가지로 응용하자