[BOJ] 2942: 퍼거슨과 사과

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

BOJ - 퍼거슨과 사과

문제 유형 : 수학

문제 난이도 : Silver II

시간 제한: 1초

메모리 제한: 128MB

 

 

문제

맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안 된다.

예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다.

1. 선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다.
2. 선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다.
3. 선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.

퍼거슨이 사과를 나누어 주는 방법을 구하는 프로그램을 작성하시오. 훈련장에 선수는 무한히 많다.

 

입력

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

 

출력

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

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

 

풀이

R과 G의 최대공약수를 구한다.

1부터 R과 G의 최대공약수까지, i(사과를 받을 선수의 수) 다음을 반복한다:

 만약 현재 수 i가 R과 G의 공약수라면, i R/i G/i를 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int R, G;
  cin >> R >> G;

  int commonDivisor = gcd(max(R, G), min(R, G));

  for (int i = 1; i <= commonDivisor; ++i) {
    if (R % i == 0 && G % i == 0) {
      cout << i << " " << R / i << " " << G / i << "\n";
    }
  }

  return 0;
}