АВТОБУСИ

면접 대비

시간 제한1초메모리 제한1024 MB

요약

세 버스의 주기 a, b, c의 최소공배수의 배수 중 d번째 날의 시간 구간 [d*t, d*t + t - 1]에 들어가는 개수를 센다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Немуш 시의 시외버스 서비스는 상황이 좋지 않다. 도시 전체에 버스 노선이 세 개뿐이고, 각 노선에는 버스가 한 대씩만 운행된다. 새해 첫날 자정 정각에 세 버스가 모두 Немуш에서 노선을 따라 출발한다. 각 버스가 노선을 끝까지 달린 뒤 도시로 돌아오는 데 걸리는 시간은 각각 a분, b분, c분이다. 따라서 첫 번째 버스는 Немуш에서 시각 0, a, 2a, 3a, ...에 출발하고, 두 번째 버스는 0, b, 2b, 3b, ..., 세 번째 버스는 0, c, 2c, 3c, ...에 출발한다.

환승하기 좋은 시각은 세 버스가 모두 Немуш에서 출발하는 시각이다. 예를 들어 a = 1, b = 2, c = 1이면 시각 0과 2는 환승하기 좋고, 시각 1은 두 번째 버스가 운행 중이므로 좋지 않다. Немуш는 시간을 특별하게 측정하는 특별한 도시이므로 Немуш의 하루는 정확히 t분이다. 따라서 첫째 날에는 시각 0부터 (t ⎼ 1)까지 모두 진행되고, 둘째 날에는 t부터 (2t ⎼ 1)까지, 셋째 날에는 2부터 (3t ⎼ 1)까지, 이런 식이다. Немуш 시청은 d번째 날에 환승하기 좋은 시각이 몇 개나 있는지 알고 싶어 한다. 아쉽게도 지역 공무원들은 다른 일로 바빠서, 이 질문에 대한 답은 여러분에게 맡겨졌다.

프로그램 bus를 작성하여 d번째 날에 환승하기 좋은 시각의 개수를 구하라.

입력

표준 입력의 처음 5개 줄에 다섯 정수 a, b, c, t, d가 주어진다. 이는 각각 첫 번째, 두 번째, 세 번째 버스가 노선을 완전히 달리는 시간, 하루의 분 수, 시청이 궁금해하는 날의 번호이다.

출력

표준 출력의 첫째 줄에 프로그램은 하나의 정수를 출력해야 한다. 이는 d번째 날에 환승하기 좋은 시각의 개수이다.

제한

1 ≤ a, b, c ≤ 106
1 ≤ t, d ≤ 109

힌트

첫 번째 예에서 하루는 3분이므로 첫째 날의 모든 시각은 0, 1, 2이다. 이 중 환승하기 좋은 시각은 0과 2이다.

두 번째 예에서는 둘째 날의 시각 7, 8, 9, 10, 11, 12, 13을 다룬다. 첫 번째 버스는 8, 10, 12에 출발하고, 두 번째 버스는 9와 12에, 세 번째 버스는 8과 12에 출발한다. 따라서 12만이 환승하기 좋은 시각이다.

세 번째 예에는 환승하기 좋은 시각이 하나도 없다.

예제3

예제 1
입력
```
1
2
1
3
1
```
예상 출력
```
2
```
예제 2
입력
```
2
3
4
7
2
```
예상 출력
```
1
```
예제 3
입력
```
2
3
4
3
3
```
예상 출력
```
0
```