백준 3955번 캔디분배

<백준 3955번 캔디분배 - 마포 코딩박>

사용한 알고리즘: 수학 ( Extended Euclidean Algorithm )


문제에서는 K 와 C 를 준 후, Cx = 1 (mod K) 를 만들 수 있는 x 를 구하는 문제였습니다.

사실 이 문제는 Extended Euclidean Algorithm 을 알아야 풀 수 있는 문제였습니다.
간단히 설명하자면, ax+by = gcd(a,b) 를 풀이하는 diopantine 방정식을 구현한 후, 이때 gcd(a,b) = 1 이라고 한다면, 이는 ax + by = 1 꼴이 되고,
이를 통해 문제에 적용하면, ax + by = Cx + M = Cx = 1 (mod M) 꼴이 됩니다.
다시말해 C와 M의 gcd가 1이 아니면 Cx = 1 (mod M) 꼴을 만족하는 x 를 찾을 수 없습니다.

구현 자체는 어렵지 않은 수학 문제였습니다.
참고로 사탕을 모든 M 명에게 나눠주고 싶기 때문에 Cx > M 이어야 합니다.