[백준/3844] 백준 공화국 (Python)

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

3844번: 백준 공화국

 

Difficulty : Gold 1

 

Status : Solved(pypy3)

 

Time : 00:36:41

 

---

 

문제 설명

 

 

백준 공화국 사람들은 매년 독립일을 기념한다. 그러나 독립이 아주 오래 전의 일이었으므로, 이젠 독립일을 정확하게 기억하는 사람은 아무도 없다. 사람들의 기억속에 남아있는 것은 독립일로부터 오늘까지의 날 수 (D) 가 완전제곱수라는 사실, 그리고 그 수가 n이하의 서로 다른 자연수의 곱으로 이루어졌고, 가능한 가장 큰 수라는 사실이다.

백준 공화국은 1년이 1,000,000,007일 이므로 사람들은 D를 1,000,000,007로 나눈 나머지가 필요하다. 다만, D를 1,000,000,007로 나눈 나머지가 가장 큰 것이 아니라 D가 가장 큰 것을 원한다.

 

 

입력 및 출력

 

입력

 

각 테스트케이스마다 한 줄 씩 n이 주어진다(1 ≤ n ≤ 10, 000, 000). 입력으로 0이 들어오면 종료한다.

 

출력

 

각 테스트케이스마다 한 줄 씩 D를 1,000,000,007로 나눈 나머지를 출력한다.

 

입력 예시

 

4
9348095
6297540
0

 

출력 예시

 

4
177582252
644064736

 

 

---

 

풀이

 

완전제곱수는 소인수분해하였을 때 각 소인수의 차수가 짝수인 특성을 지닌다. 또한, 주어진 n에 대하여 (n // 2)까지의 소수가 소인수 후보가 될 수 있다.

즉 정리하면

 

• 소인수 리스트를 구하기 위해 에라스토테네스의 체를 사용한다. 시간복잡도는 O(nloglogn) 이 된다.
• 위에서 구한 소인수 리스트에 속한 수를 i라고 두자. 1부터 n까지의 수를 모두 곱했을 때, i의 총 차수를 알아야 한다.
  • i, i^2, i^3... 순으로 n을 나눈 몫의 합이 총 차수가 된다 (이전에 다루었던 문제에 있었던 설명같은데....)
  • 예를 들어 보자. n = 8이고 i = 2일때,
    • i를 인수로 갖는 목록 : 2, 4, 6, 8 -> 8 // 2 = 4
    • i^2를 인수로 갖는 목록 : 4, 8 -> 8 // 4 = 2
    • i^3를 인수로 갖는 목록 : 8 -> 8 // 8 = 1
  • 로 총 차수는 7이다.
• 만약 총 차수가 홀수라면, 차수를 1 빼주는 것과 동일하다. 이는 [1, n] 후보군 리스트 안에서 i를 인수로 갖는 가장 작은 수인 i 자체를 제거하는 것과 동일하다.
• 이제 i의 총 차수 제곱을 곱해주면 된다.
  • 총 차수의 제곱값은 매우 클 수 있다. 즉 분할 정복을 통한 거듭제곱을 사용해야 한다.     

 

풀이 코드

import sys
input = sys.stdin.readline
MOD = 1000000007
MAX = 10000000

def erastothenes(bound) :
  nums = [True]*(bound+1)
  for i in range(2, bound+1) :
    if nums[i] :
      for j in range(i+i, bound+1, i) :
        nums[j] = False
  return nums

def pow(n, k) :
  if k == 0 :
    return 1
  if k == 1 :
    return n
  p = pow(n, k // 2)
  p = (p * p) % MOD
  if k % 2 :
    p = (p * n) % MOD
  return p

def solve() :
  n = int(input())
  if n == 0 :
    return False
  result = 1
  for i in range(2, n//2+1) :
    if not nums[i] :
      continue
    cnt = 0
    j = i
    while j <= n :
      cnt += n // j
      j *= i
    if cnt % 2 :
      cnt -= 1
    result = (result * pow(i, cnt)) % MOD
  print(result)
  return True

nums = erastothenes(MAX//2)
while solve() :
  continue

풀이 완료!