음식 평론가

summary:

소시지 n개를 평론가 m명에게 나누어 줄 때, 몇번 칼질을 해야 하는가?

solution:

평론가가 줄서서 한명씩 소시지를 잘라서 가져간다고 생각해 보면 i번째 평론가가 가져갈 때마다 i*(n/m)만큼의 소시지가 없어진다.

그런데 만약에 i*(n/m)이 자연수라면 자를 필요가 없다.

자연수인 경우는 gcd(n,m)번 있다. 따라서 평론가의 수(m) - 자를 필요가 없는 경우(gcd(n,m))이 답이 된다.