[백준] 1188 - 음식 평론가

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

1188번: 음식 평론가

 

모든 음식 평론가가 받는 소시지의 길이는 N / M으로 같다.

그렇다면 처음 모든 소시지를 1열로 나열해보자.

최대 M - 1번으로 자르면 M명의 평론가에게 나누어 줄 수 있다.

하지만 N = 4, M = 6인 경우에는 4번만 잘라도 6명의 평론가에게 나누어 줄 수 있게 된다.

 

N = 4, M = 6인 경우에는 2개의 소시지에 3명씩 배분하는 경우의 수를 두배 하면 된다.

N = 6, M = 9인 경우에는 2개의 소시지에 3명씩 배분하는 경우의 수를 세배하면 된다.

 

결국, 답은 M - GCD(N, M) 이다.

 

#include <iostream>
using namespace std;

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

int main() {
	int a, b; cin >> a >> b;
	if (a % b == 0) {
		cout << 0;
	}
	else {
		cout << b - gcd(a, b);
	}
}