[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;
}