[백준] 2904 수학은 너무 쉬워💫

백준 2904 수학은 너무 쉬워

• https://www.acmicpc.net/problem/2904

• N개의 숫자들의 최대공약수가 최대인 경우는 N개의 숫자들을 소인수분해 했을 때 소수들을 최대한 균등하게 가지고 있는 경우이다.

작성한 코드

• 왜 틀렸는지 아직 잘 모르겠다. 천천히 더 생각해봐야지

#include <iostream>
#include <math.h>
#include <memory.h>
using namespace std;

//test
//input:
//5
//4 5 6 7 8
//answer:
//2 2


//1 ~ 1000000 사이 소수의 개수  = 78498
int minFactor[1000005];
int num[100];

//num이 가진 소수의 개수
int havePrime[100][78500];

//최종 상태에서 num 가져야할 소수의 최소 개수
int finalPrime[78500];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//에라토스테네스의 체 변형
	memset(minFactor, 0, sizeof(minFactor));
	minFactor[0] = minFactor[1] = -1;

	for (int i = 2; i <= 1000000; i++)
		minFactor[i] = i;

	int sqrtn = sqrt(1000000);
	for (int i = 2; i <= sqrtn; i++) 
		if (minFactor[i] == i)
			for (int j = i * i; j <= 1000000; j += i)
				if (minFactor[j] == j) minFactor[j] = i;
	
	//수 입력받기
	int n;
	cin >> n;

	memset(num, 0, sizeof(num));
	for (int i = 0; i < n; i++)
		cin >> num[i];

	//소인수 분해
	for (int i = 0; i < 100; i++)
		memset(havePrime[i], 0, sizeof(havePrime[i]));

	//배열 탐색 범위를 줄이기 위해 소수의 최댓값 저장
	int maxPrime = 0; 
	for (int i = 0; i < n; i++) {
		int tmp = num[i];
		while (tmp > 1) {
			if (maxPrime < minFactor[tmp]) maxPrime = minFactor[tmp];

			havePrime[i][minFactor[tmp]]++;
			finalPrime[minFactor[tmp]]++;

			tmp /= minFactor[tmp];
		}
	}

	//점수 구하기
	int score = 1;
	for (int p = 2; p <= maxPrime; p++) {
		finalPrime[p] /= n;
		score *= pow(p, finalPrime[p]);
	}

	//소수 배분하기
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int p = 2; p <= maxPrime; p++) {
			if (havePrime[i][p] < finalPrime[p])
				cnt += (finalPrime[p]- havePrime[i][p]);
		}
		
	cout << score << " " << cnt;
	return 0;
}