[Atcoder] ABC 280 - D. Factorial and Multiple

https://atcoder.jp/contests/abc280/tasks/abc280_d

D - Factorial and Multiple

---

 

22/12/03

 

 

업솔빙을 하며 개인적으로 백준의 8279번이 많이 떠올랐던 문제였다.

 

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

8279번: Double Factorial

 

아이디어가 비슷한 문제인데, 8279번 같은 경우, 공식을 통해 for문을 최소화하는 방향으로 해결했다.

 

이 문제도 비슷하게 할 수 있을 것 같았지만 방법이 떠오르지는 않아서 그렇게 하진 못했다.

---

 

문제 접근 방식:

 

 

문제에서 요구하는 사항은 어떤 임의의 수 $K$가 주어질 때, $N!$이 $K$의 배수가 되도록 하는 최소의 $N$값을 구하는 것이다.

 

물론 악으로 깡으로 $K$의 배수가 될 때까지 $N!$을 일일이 구하는 건 바보같은 짓이다.

 

먼저 케이스를 좀 나눠야될 필요가 있다.

 

1. $K$가 소수인 경우

 

이 경우 $N!$이 이 소수를 포함하려면 당연히 $K$까지 곱해야되므로, $N = K$가 된다.

 

2. $K$가 소수가 아닌 경우

 

이 경우 $N!$이 $K$의 배수가 되려면, $N!$을 소인수 분해 했을 때의 리스트가 $K$을 소인수 분해 했을 때의 리스트보다 더 커야된다.

 

 

1번 경우는 쉽게 구할 수 있지만, 2번 경우는 최솟값을 일일히 $N$에 $+1$을 해가며 구하면 시간초과가 나버린다.

 

이를 해결하기 위해서는 다음과 같은 아이디어를 활용해야 한다.

 

먼저, $K$를 소인수 분해한 리스트에 소수가 종류 별로 몇 개 있는지 세어줘야한다.(이는 파이썬의 Counter함수로 해결 가능)

 

$$K = {p_1}^{a_1}{p_2}^{a_2}...{p_k}^{a_k}$$

 

 

이후 각 소수 $p_1$, $p_2$, $...$, $p_k$별로 반복문을 돌린다.

 

우리는 $N!$을 소인수 분해 했을 때, 그 소수의 빈도수만큼 $N!$이 그 소수를 가지고 있어야 한다는 사실을 알고 있다.

 

다시 말해, $p_1$의 경우라면, $N!$이 적어도 $a_1$개 이상의 $p_1$을 가지고 있어야 한다.

 

이렇게 되도록 하는 최솟값을 각 소수 별로 구해준다.

 

 

최솟값을 구하는 방법은, 다음과 같다.

 

예를 들어 $p_1$을 가지고 반복문을 돌린다고 한다면, 먼저 $p_1$에서 시작하여 $p_1$씩 늘려가며 그 숫자가 몇 개의 $p_1$을 포함하고 있는지 확인해 준다.

 

이후 지금까지의 숫자가 몇개의 $p_1$을 가지고 있는지 확인해주어서, 만약 넘어가거나 같아지면 멈추면 된다.

 

 

말로만 하면 설명이 잘 안되므로 예시를 한번 들어보자.

 

예를 들어 $K = 3^{10}$이라고 해보자.

 

그러면 $N!$을 소인수 분해 했을 때, $3$을 $10$개 이상 가지고 있어야 하므로, $N$의 후보로 될 수 있는 것들은 $3$의 배수일 것이다.

 

그래서 $3$의 배수를 돌려가며 확인해보자.

 

$N = 3$이면, $N!$을 소인수 분해하면 $3$이 하나 존재한다.

 

$N = 6$이면, $N!$을 소인수 분해하면, $3$이 $1 + 1$개 존재한다.($N!$이 $3$과 $2*3$을 포함하므로)

 

$N = 9$이면, $N!$을 소인수 분해하면, $3$이 $1 + 1 + 2$개 존재한다.

 

이런 식으로 소수의 배수를 돌려가며 지금까지 몇개의 소인수가 나왔는지 세주면 된다.

 

 

 

이후, 이 최솟값들의 최댓값을 구해주면 된다.

 

최솟값들의 최댓값을 구하는 이유는, 최댓값을 취하면 팩토리얼의 정의에 의해 그 이전의 숫자들을 다 곱해주기 때문에 이미 다 포함이 될 수 있기 때문이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

import sys
input = sys.stdin.readline
from collections import Counter
from math import factorial

def factoring(num):
    ftr = []
    i = 2
    number = num
    while i <= num**(1/2):
        while number % i == 0:
            number //= i
            ftr.append(i)
        i += 1
    if number != 1:
        ftr.append(number)
    return ftr
K = int(input())
factor = factoring(K)
if len(factor) == 1:
    print(factor[-1])
else:
    factor = Counter(factor)
    num_li = []
    for prime, frequency in factor.items():
        num = prime
        cnt = 1
        while cnt < frequency:
            num += prime
            n = num
            i = 0
            while n % prime == 0:
                n //= prime
                i += 1
            cnt += i
        num_li.append(num)
    print(max(num_li))