[백준oj] 1188번 음식 평론가

www.acmicpc.net/problem/1188

1188번: 음식 평론가

---

 

평론가들은 소세지를 각각 N/M개씩 노나먹는다. N개의 소세지가 일렬로 붙어있다고 가정을 하면, 칼질은 M-(N과M의 최대공약수)만큼 칼질을 하면된다.

 

#include<iostream>

using namespace std;

int n, m;

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

int main() {
	cin >> n >> m;
	cout << m - gcd(n, m);
}