2853 배

여러 배들이 일정한 간격으로 돌아온다고 할 때, 배가 한척이라도 돌아온 날을 기록한다.
그 기록을 가지고 배가 최소 몇대있는지를 구하는 문제이다. 첫날엔 모든 배가 동시에 도착했다고 가정한다.

만약 배가 2일 주기로 온다면, 첫날을 0일이라 할 때, 2 4 6 8.. 일에 도착할 것이다.
같은 원리로 배가 n일 주기로 온다면 n, 2n, 3n, ... 일에 도착한다.

따라서 배가 돌아온 날짜를 하나씩 저장하면서 현재도착한 날짜가 이전에 도착한 날짜와 나누어 떨어진다면, 이 배는 예전에 왔던 배로 간주하여 카운트 하지 않는다. 그 외엔 카운트 해주면, 배의 개수의 최소를 구할 수 있다.

소스