백준 2904번, 수학은 너무 쉬워 풀이

문제

백준 2904번

풀이

$A$를 나눌 수 있는 $X$는 $A$의 소인수를 의미합니다.

이 점을 유의해서 문제를 접근해봅시다.

 

연산을 잘 실행해준 뒤 각 수들의 최대공약수를 최대화하려면,

모든 수들의 소인수를 골고루 분배해주면 됩니다.

 

예를 들면, $2^5 \cdot 3^1$과 $2^1 \cdot 3^3 $라는 두 수가 있다고 생각해봅시다.

소인수 2는 총 6개, 3은 4개가 있습니다.

이제 위 소인수들을 골고루 분배하면, 각각의 수는 $2^3 \cdot 3^2$이 됩니다.

 

위 방법(모든 수의 소인수 개수를 세는 것)으로 최대공약수를 최대화할 수 있는데,

몇 번을 움직여야 하는지도 구해야합니다.

 

예를 들어서,

$2^5 \cdot 3^1 \cdot 5^3$이라는 수가 있고,

위에서 구한 최대공약수가 $2^3 \cdot 3^2$라고 해봅시다.

현재 수를 위 최대공약수의 배수로 만들되 소인수들을 골고루 분배한다면,

이 수에서 $2^2$는 다른 수에 주면 되고, $3^1$은 다른 수로부터 받으면 되고,

$5^3$은 움직이는 수를 최소화해야 하므로 그대로 나둬야 합니다.

 

즉, 최대공약수의 소인수만 확인하면서 개수를 맞춰주면 됩니다.

이 과정에서 중복으로 세지 않도록, 항상 큰 쪽에서 작은 쪽으로 옮겨주는 방향만 세면 깔끔하게 구해집니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

vi prime;
int vis[1000001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (int i = 2; i <= 1e3; i++) {
		if (vis[i]) continue;
		prime.emplace_back(i);
		for (int j = i; j <= 1e3; j += i) vis[j] = 1;
	}

	map<int, int> cnt;
	auto extract = [&](int a) {
		map<int, int> curr;
		for (const auto &p : prime) {
			if (a == 1) break;
			while (a % p == 0) a /= p, cnt[p]++, curr[p]++;
		}
		if (a > 1) cnt[a]++, curr[a]++;
		return curr;
	};

	int n;
	cin >> n;
	vector<map<int, int>> vec(n);
	for (auto &i : vec) {
		int a;
		cin >> a;
		i = extract(a);
	}

	map<int, int> goal;
	ll ans = 1, mv = 0;
	for (const auto &[i, c] : cnt)
		if (c / n) goal[i] = c / n, ans *= powl(i, c / n); //소인수의 개수 / n하는 것이 가장 골고루 나누는 것
	cout << ans << " ";
	for (auto &i : vec) { //i번째 수의 소인수가 저장된 테이블
		for (const auto &[j, c] : goal) //j는 최대공약수의 소인수, c는 소인수 j의 개수
			if (c > i[j]) mv += c - i[j]; //i번째 수의 소인수 j의 개수를 c로 맞춰준다.
	}
	cout << mv;
}