[BJ1037] 약수 풀이

백준 1037 약수 풀이

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

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

---

풀이

단순한 정수론 문제로 임의의 숫자 N에 대해서 1과 자기 자신을 제외한 모든 약수가 주어집니다. 처음에 풀 때 어렵게 최대공약수나 최소공배수 등을 이용해서 풀어야하는가 싶었지만, 생각해보니 가장 큰 약수와 가장 작은 약수의 곱이 항상 N을 만든다는 것을 알 수 있었습니다.

좀 더 자세하게는 진짜 약수의 개수가 2개 이상인 경우(즉, 1과 N을 제외한 약수가 2개 이상)에는 무조건 가장 큰 약수($$f_max$$)와 가장 작은 약수($$f_min$$)의 곱으로 N을 만들 수 있습니다. $$ \frac{N}{f_{min}} = f_max $$

진짜 약수의 개수가 1개인 경우에도 성립합니다.
예를 들어 4의 경우에는 진짜 약수가 2 하나 밖에 없는데 최소 약수와 최대 약수 모두 2이므로 둘의 곱은 4입니다.

소스 코드

//cpp
#include <iostream>

using namespace std;

int main(){
    // 입출력을 빠르게 하는 구문
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int N; cin >> N;

    // 32비트 부호잇는 정수가 출력값이므로 안전하게 64비트 부호없는 정수를 사용
    unsigned long long max = 0; // unsigned이므로 max에 -1을 넣으면 오버플로 & 입력값의 최소값이 2
    unsigned long long min = 987654321; // 입력값의 최대값이 1000000 & 습관적으로 987654321 사용
    int input;
    // 입력 값 중에 최대값과 최소값을 찾는 구문
    for(int i = 0; i < N; i++){
        cin >> input;
        max = max < input ? input : max;
        min = min > input ? input : min;
    }
    // 디버깅 용도
    // cout << max << " " << min << '\n';
    cout << max * min << '\n';
}