[BOJ] 퍼거슨과 사과(2942)

[백준(BOJ)] 퍼거슨과 사과(2942) C++

문제 : BOJ_2942번 퍼거슨과 사과

문제 설명

수학, 유클리드 호제법

두 수인 R,G가 주어지면, 두 수를 모두 나눌 수 있는 수와 그 수로 R,G가 나누어진 값을 출력하는 문제입니다.

---

Solution

결국 최대공약수를 구하고 그 최대 공약수의 약수를 구해야하는 문제임으로 유클리드 호제법을 이용해 최대공약수를 구하고,
R,G가 최대 10억이기 때문에 단순한 반복문으론 시간초과 임으로 루트 N번까지만 보면되는 약수의 성질을 이용하여 루트 N번만에 구할 수 있습니다.

---

Description

1. 루트 N번만에 구하기 위해, (최대공약수/주어진 약수)를 최대공약수로 다시 나눠서 출력해야합니다. (이 때 주어진 약수 == (최대공약수/주어진 약수)인 경우 주의!)
   
2. 문제에도 주어졌고, 스페셜 저지이기 때문에 출력의 순서는 상관 없습니다.
   

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(void) {
    int r, g;
    int res_r, res_g;
    scanf("%d%d", &r, &g);
    res_r = r;
    res_g = g;
    if (r < g) swap(r, g);
    while (g) { // 유클리드 호제법
        int temp = r;
        r = g;
        g = (temp % g);
    }
    for (int i = 1; i <= sqrt(r); i++) {
        if ((r % i) == 0) {
            printf("%d %d %d\n", i, res_r / i, res_g / i);
            if(i!=(r/i))printf("%d %d %d\n", r / i, res_r / (r / i), res_g / (r / i));
            // 이 때 주어진 약수 != (최대공약수/주어진 약수) 일 때,
        }
    }
    return 0;
}