백준 2904 (C++) 수학은 너무 쉬워

최초 업로드: 2025-10-18 15:34:49

최근 수정 시간: 2025-10-18 15:35:14

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 수학은 너무 쉬워

[문제 링크](https://www.acmicpc.net/problem/2904)

## 문제 설명

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

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

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

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

## 입력

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

## 출력

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

## 풀이
각각의 수를 소인수분해를 해서 모두에게 동등하게 나누어주면 됩니다. 먼저 공통된 최대 공약수를 구해주고, 각 소수들이 등장한 횟수를 세서 전체에 잘 나누어주는 방식으로 구현했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, arr[100], divCnt[100];

ll gcdTotal() {
 ll gcdVal=arr[0];
 for(int i=1;i<n;i++) gcdVal = gcd(gcdVal, arr[i]);
 for(int i=0;i<n;i++) arr[i]/=gcdVal;
 return gcdVal;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n;
 for(int i=0;i<n;i++) cin >> arr[i];

ll res=gcdTotal(), cnt=0;
 for(int i=2;i*i<=1'000'000;i++) {
 int cur=0;
 memset(divCnt, 0, sizeof divCnt);
 for(int j=0;j<n;j++) {
 while(arr[j]%i==0) {
 cur++;
 divCnt[j]++;
 arr[j]/=i;
 }
 }

cur/=n;
 if(cur) {
 for(int j=0;j<n;j++) cnt += max(cur-divCnt[j], 0LL);
 while(cur--) res*=i;
 }
 }
 cout << res << ' ' << cnt;
}
```