[C/C++] BOJ #1037 - Divisors

BOJ #1037 is a problem related to divisors and number properties.

 

The problem provides a list of divisors of a certain positive integer N, except for 1 and N itself. The task is to determine the actual value of N using only the given divisors. The key observation is that the smallest and largest divisors in the given list, when multiplied together, yield N. This is because if all the divisors are provided (excluding 1 and N), the smallest divisor must be the smallest prime factor of N, and the largest divisor must be the largest factor of N that is not itself. By multiplying these two numbers, we can reconstruct N. The problem essentially tests the understanding of factors and basic number theory concepts, specifically the properties of divisors.

---

In the early stages of learning C/C++, common practice problems often include finding divisors and determining prime numbers. Finding divisors is straightforward as long as you understand how to use the modulo (%) operator.

This problem requires us to determine the original number N given a list of its divisors, excluding 1 and N itself, and presented in no particular order. The standard approach would involve finding the least common multiple (LCM). However, there is a simpler way to solve this problem. Since all divisors are provided, we can identify the smallest and largest numbers in the list and multiply them together to easily obtain N.

---

divisors

Below is the source code I wrote. It is provided for reference purposes only.

//----------------------------------------------------------
//    baekjoon #1037 - Divisors
//        - by Aubrey Choi
//        - created at 2019-07-03
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, s;
    long long min, max;
    scanf("%d%d",&n,&s);
    min = max = s;
    while(--n)
    {
        scanf("%d", &s);
        if(s < min) min = s;
        if(s > max) max = s;
    }
    printf("%lld\n", min*max);
}