[Java] 백준 3964번 : 팩토리얼과 거듭제곱

문제

3964번: 팩토리얼과 거듭제곱

---

 

접근 방법

1. 먼저 k의 거듭제곱은 어떤 소수로 이루어져있는지 구하기 위해 최대 10^12의 제곱근인 10^6까지 소수를 구합니다.

2. 소수를 구해놓고 k를 돌며 어떤소수와 몇 제곱으로 이루어져 있는지를 map에 집어넣습니다. ex) k가 10이면 (2,1), (5,1)이 map에 존재합니다.

3. map에서 하나씩 꺼내어 n!에서 소수로 나누고, 지수로 한번더 나누어줍니다. 그중 최소값이 정답입니다.

ex) n이 10 !, k가 40이라면 k  = 2^3 * 5^1로 이루어져 있습니다. 따라서 2,3이 map에 저장되고 countFactory메서드에 의해 8이 나와서 3으로나누어  2가 min에 저장되고, 그 이후  5가 들어가고 1이 나오기 때문에 1/1로 1이 min에 들어가게 됩니다. 따라서 10!과 40은 1이 정답이 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int T;
    private static long N,K;
    private static boolean[] isPrime = new boolean[1000010];
    private static ArrayList<Long> primes = new ArrayList<Long>();
    
    //에라토스테네스의 체(소수 구하기)
    public static void eratosthenes(){
        isPrime[0] = isPrime[1] = false;

        for(long i = 2; i <= 1000000 ; i++){
            if(!isPrime[(int)i]) continue;

            primes.add(i);

            for(long j = i*i ; j <= 1000000; j+=i){
                isPrime[(int)j] = false;
            }
        }
    }

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        Arrays.fill(isPrime, true);
        eratosthenes();

        for(int tc = 0 ; tc < T ; tc++){
            st = new StringTokenizer(br.readLine());

            N = Long.parseLong(st.nextToken());
            K = Long.parseLong(st.nextToken());

            process();
        }
    }
    
    //map에 소수와 지수를 넣어줍니다.
    public static Map<Long,Integer> primeCount(long k){
        Map<Long,Integer> count = new TreeMap<>();

        for(long prime : primes){
            if(prime * prime > k) break;

            int cnt = 0;
            while(k%prime == 0){
                cnt++;
                k/=prime;
            }
            if(cnt>0){
                count.put(prime,cnt);
            }
        }
        if(k>1){
            count.put(k,1);
        }

        return count;
    }
    
    //n!을 prime으로 나누면 해당하는 prime이 몇 개 존재하는지 나타남
    public static long countFactorial(long n, long prime){
        long count = 0;
        while(n >= prime){
            count += n/prime;
            n /= prime;
        }
        return count;
    }

    //실행
    public static void process() {
        Map<Long,Integer> primeCheck = primeCount(K);
        long min = Long.MAX_VALUE;

        for(Map.Entry<Long,Integer> entry : primeCheck.entrySet()){
            long prime = entry.getKey();
            int cnt = entry.getValue();

            min = Math.min(min, countFactorial(N,prime)/cnt);
        }
        sb.append(min).append("\n");
    }


    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}