2942 - 퍼거슨과 사과

1. 문제 조건 확인

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

빨간 사과 R개와 초록 사과가 G개 있다. 이를 몇몇 선수들에게 나누어 주는데, 받은 선수들은 모두 같은 수의 사과를 가져야 한다. 또한 사과를 나누어 준 뒤에 사과가 남아서는 안된다. 선수는 무한히 존재한다.

입력 조건

빨간 사과의 수 R과 초록 사과의 수 G가 주어진다. R, G 모두 10^9이하의 자연수이다. 즉, INT 범위 이내이다.

출력 조건

사과를 나누는 방법을 모두 출력한다. 그 형식은 (N X Y)로 모든 경우를 한 줄 씩 출력한다.

N은 선수의 수, X와 Y는 각 선수가 받는 빨간 사과와 초록 사과의 수이다.

ex) 빨간 사과 4개, 초록 사과 8개인 경우

   예시 출력:1 4 8

2 2 4  

4 1 2

2. 문제 풀이

아이디어

두 개의 사과 그룹이 있고, 사과를 나누어 주는데, 두 개의 그룹 모두에서 사과가 남으면 안된다. 즉, 두 그룹의 사과 수를 나누어 모두 나머지가 없어야 한다. 다시 말해서 빨간 사과의 수 R과 초록 사과의 수 G의 공약수를 찾으면 해결할 수 있는 문제이다. R과 G의 공약수를 찾기 위해서 우선 최대공약수를 찾고, 최대공약수로 부터 공약수를 찾아 출력하자. 출력 순서가 크게 상관이 없으므로, 공약수를 찾을 때마다 그 답을 출력해주면 된다.

코딩

앞서 말했듯이, 우선은 최대공약수를 찾는다. 최대공약수를 찾는 법은 유클리드 호제법을 사용한다.

유클리드 호제법을 사용해서 최대공약수를 찾았다면, 이제 공약수를 찾는다. 이 때 두 수의 공약수는 최대공약수의 약수와 동일한 점을 이용해서, 공약수를 찾도록 한다.

최대공약수의 약수를 찾는 법은 간단하다. 최대공약수를 1부터 나누면서 제수가 몫보다 같거나 작은 경우인 동안 반복한다. 그리고 최대공약수가 제수로 나누어 떨어지는 경우에만 출력한다.

예를 들어, 12의 경우 (제수, 몫)을 찾게되면, (1,12),(2,6),(3,4) 이다. -> 다음의 경우는 (4,3)이므로 불가능!

한 가지 더, 36의 경우 (제수, 몫)을 찾게되면, (1,36),(2,18),(3,12),(4,9),(6,6)이다.

#include<stdio.h>
 
int main(void) {
    int r, g;
 
    scanf("%d %d", &r, &g);
 
    //Find the GCD
    int dividend, divisor, remainder;
    if (r > g) {
        dividend = r;
        divisor = g;
    }
    else {
        dividend = g;
        divisor = r;
    }
    do {
        remainder = dividend % divisor;
        dividend = divisor;
        divisor = remainder;
    } while (remainder != 0); 
    int gcd = dividend;
    int cd = 1; 
    while (cd * cd <= gcd) {
        if (gcd % cd == 0) {
            int cd_big = gcd / cd;
            printf("%d %d %d\n",cd,r/cd,g/cd);
            if(cd != cd_big) printf("%d %d %d\n",cd_big,r/cd_big,g/cd_big);
        }
        
        cd++;
    }
 
    return 0;
}