fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 2904 (C++) 수학은 너무 쉬워
최초 업로드: 2025-10-18 15:34:49
최근 수정 시간: 2025-10-18 15:35:14
게시자: rlatjwls3333
카테고리: 백준
조회수: 8
# [Gold III] 수학은 너무 쉬워 [문제 링크](https://www.acmicpc.net/problem/2904) ## 문제 설명 <p>상근이의 할머니는 매우 유명한 수학자이다.<span class="Apple-tab-span" style="white-space:pre"> </span>할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.</p> <p>두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.</p> <p>상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.</p> <p>상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.</p> ## 입력 <p>첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.</p> ## 출력 <p>첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다. </p> ## 풀이 각각의 수를 소인수분해를 해서 모두에게 동등하게 나누어주면 됩니다. 먼저 공통된 최대 공약수를 구해주고, 각 소수들이 등장한 횟수를 세서 전체에 잘 나누어주는 방식으로 구현했습니다. ``` 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; } ```