캔디 분배

summary:

k명에게 한 개 이상의 사탕을 줘야 하고, 예비용으로 1개 추가하여 kx+1= cy 가 되게 하는 (x,y)쌍을 찾는 문제.

solution:

확장 유클리드 알고리즘 을 사용해서 풀면 되는 문제다.

kx+1=cy

cy-kx=1이므로

k와 c의 gcd가 1이라면 kx+cy=gcd(k,c)의 형태가 되므로 풀 수 있게 된다.

따라서 k와 c의 gcd를 먼저 확인해주고(1인지 아닌지) , 확장 유클리드 알고리즘으로 x,y쌍을 구한 뒤 문제 조건에 맞게 수정해주면 된다.