8회차 - 공약수 게임

평소 모든 게임을 다 잘하는 예인이는 게임의 여왕으로 불린다. 하지만 이번 MT에서 똑똑한 수정이가 준비한 게임은 수학적인 아이디어를 요구하기 때문에 애를 먹고 있다. 수정이가 준비한 게임은 아래와 같은 규칙으로 진행된다.

• 게임을 하는 참가자는 가장 먼저 자연수가 적힌 카드 N개를 받는다.
• 참가자는 자신이 원하는 횟수만큼 아래의 동작을 반복할 수 있다.
• 게임이 종료될 때 각 사람은 자신이 들고있는 카드들에 적힌 숫자들 전부의 최대공약수 만큼 점수를 획득한다.

 

 예인이는 제한 시간동안 마구잡이로 여러 방법을 시도해보고 있지만, 자신이 얻은 점수가 높은 점수인지 확신을 할 수 가 없었다. 예인이를 도와서 처음에 주어진 숫자 카드를 통해 얻을 수 있는 최고의 점수를 계산하는 프로그램을 작성해주자.

 

입력 형식

  첫 줄에는 처음에 주어지는 숫자 카드의 수 N이 주어진다. N은 1이상 100이하의 자연수이다. 

 두 번째 줄에는 총 N개의 카드에 적혀있는 숫자가 주어진다. 처음 카드에 적혀있는 숫자는 100만이하의 자연수이다.

 

출력 형식

 예인이가 얻을 수 있는 최대의 점수를 한 줄에 자연수로 출력한다.

 

문제 출처

• Croatian Open Competition in Informatics 2009/2010, Contest #4, Problem #3

 

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);
	public static final int MAX_VALUE = 1000000;


	/**
	 * 게임의 규칙을 만족하면서 만들 수 있는 가장 큰 최대공약수를 반환하는 함수
	 *
	 * @param n         주어진 카드의 수
	 * @param cards     각 카드에 적힌 숫자 배열
	 * @return
	 */
	public static int getMaximumGCD(int n, int[] cards)
	{

		int answer = 1;
		int[] frequency = new int[MAX_VALUE+1];
		
		// 소인수분해를 한다. 
		for(int C : cards){ // 모든 카드에 대해
			ArrayList<Long> factors = MathUtil.factorize(C); // 소인수 분해
			
			// 모든 소인수에 대해
			for(long f : factors){
				frequency[(int)f] += 1;
			}
		}

		for( int i = 2; i <= MAX_VALUE; i += 1){
			// 모든 소인수 i 에 대해
			// 어차피 소인수 아니면 빈도수 0일꺼라 skip
			if(frequency[i] == 0){
				continue;
			}
			
			int count = frequency[i] / n;
			answer *= MathUtil.powInt(i, count);
		}
		return answer;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();
		int[] cards = new int[n];
		for(int i = 0 ; i < n ; i++)
		{
			cards[i] = scanner.nextInt();
		}

		int answer = getMaximumGCD(n, cards);

		System.out.println(answer);
	}

}

class MathUtil{
	/**
	 *
	 * @param N
	 * @return
	 */
	public static ArrayList<Long> factorize(long N) // 최몇
	{
		ArrayList<Long> factors = new ArrayList<>();
		
		for( long div = 2; div * div <= N; div += 1){
			while(N % div == 0){
				factors.add(div);
				N /= div;
			}
		}
		if( N > 1 ){
			factors.add(N);
		}
		return factors;
	}


	/**
	 * 두 정수 a, n에 대해 a ^ n을 계산해주는 함수
	 *
	 * @param a
	 * @param n
	 * @return
	 */
	public static int powInt(int a, int n)
	{
		int result = 1;
		for( int i = 0; i < n; i++ ){
			result *= a;
		}
		return result;
	}
}