백준 2942번[c언어] : 퍼거슨과 사과

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

2942번: 퍼거슨과 사과

---

풀이

• 색깔이 다른 사과를 같은 개수대로 받아야 하며 사과의 개수는 남지않아야 한다.
• 사과가 남지 않게 나누어주려면 (약수) 명에게 나누워줘야 사과의 개수가 남지 않는다
• 약수 중 가장 큰 수는 최대공약수로 앞서 최대공약수를 구하는 함수 문제를 풀었다.
• 최대공약수를 구해 for(int i=1부터 최대공약수 까지) 진행하며 n%i==0이라면 사과의 개수는 나누어 떨어지지 않게된다.
• 선수들에게 나누워줄 수 있는 사과의 개수는 n/r개와 n/g개이다.

#include<stdio.h>
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int main() {
    int r, g, n;
    scanf("%d %d", &r, &g);
    n = gcd(r, g);
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            printf("%d %d %d\n", i, r / i, g / i);
        }
    }
}