백준] 2942 - 퍼거슨과 사과(COCI 2008/2009)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 R과 G가 주어진다. (1 ≤ R, G ≤ 1,000,000,000)

출력

퍼거슨이 사과를 나누어 주는 방법을 출력한다. 방법을 출력할 때는 사과를 받게되는 선수의 수 N과 나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력한다.

각 방법은 한 번만 출력해야 한다. 나누어 주는 방법은 아무 순서로 출력해도 된다.

소스코드

#include <math.h>
#include <iostream>
#include <set>
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a%b);
}
int main(void)
{
	int r, g, c;
	set<int> meta;
	cin >> r >> g;

	if (r > g)
		c = gcd(r, g);
	else
		c = gcd(g, r);

	for (int i = 1; i <= sqrt(c); i++)
	{
		if (c%i == 0)
		{
			if (c / i == i)
				meta.insert(i);
			else
				meta.insert(i), meta.insert(c / i);
		}
	}

	for (set<int>::iterator iter = meta.begin(); iter != meta.end(); iter++)
		cout << *iter << ' ' << r / (*iter) << ' ' << g / (*iter) << '\n';
}

Tip

두 사과의 개수의 공약수들이 퍼거슨이 사과를 나눠주는 방법이다. 일단 유클리드 호제법으로 최대공약수를 구하고 약수들을 구해나가는 방식으로 접근했다. 처음에 문제를 잘못 이해하고 제시된 방법으로만 나누는 걸로 풀어서 두 번이나 틀려버렸다..