백준 2904번 : 수학은 너무 쉬워 (c++)

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

2904번: 수학은 너무 쉬워

문제

상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.

두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.

상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.

상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.

입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.

출력
첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다.

예제 입력 1 
3
8 24 9
예제 출력 1 
12 3

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>

using namespace std;

int N, M;
bool visited[1001];
vector <int> prime;
map <int, int> A,B,C;
vector <int> num;

void chk(int n) {
	for (auto it : prime) {
		if (n % it == 0) {
			A[it]++;
			chk(n / it);
			return;
		}
	}
	if (n != 1) {
		A[n]++;
	}
}

void chk2(int n) {
	for (auto it : prime) {
		if (n % it == 0) {
			B[it]++;
			chk2(n / it);
			return;
		}
	}
	if (n != 1) {
		B[n]++;
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for (int  i = 2; i < 1001; i++)
	{
		if (!visited[i]) {
			prime.push_back(i);
			for (int j = 2; i*j < 1001; j++)
			{
				if (visited[i * j] == 0) {
					visited[i * j] = true;
				}
			}
		}
	}
	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> M;
		num.push_back(M);
		chk(M);
	}

	long long total = 1;
	for (auto i : A) {
		int h = i.second / N;
		while (h--) {
			total *= i.first;
		}
	}

	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		B.clear();
		chk2(num[i]);
		for (auto it : A) {
			int now = it.first;
			if (B[now]<it.second/N) {
				cnt += (it.second / N) - B[now];
			}
		}
	}
	cout << total << " " << cnt;
	return 0;
}