등차수열과 등비수열

등차수열 $A$의 일반항은 $a + b \times x$이고, 등비수열 $G$의 일반항은 $c \times d^y$이다. 여기서 $x$와 $y$는 음이 아닌 정수이다.

$a$, $b$, $c$, $d$, $u$가 주어졌을 때, $1$ 이상 $u$ 이하의 정수 중에서 $A$나 $G$에 속하는 수가 몇 개인지 구하는 프로그램을 작성하시오. 두 수열에 동시에 속하는 수도 센다. 같은 수가 수열에 여러 번 나타나더라도 개수는 한 번만 센다.

첫째 줄에 $a$, $b$, $c$, $d$, $u$가 공백으로 구분되어 주어진다. ($1 \le a, b, c, u \le 10^{12}$, $1 \le d \le 10^5$)

첫째 줄에 $1$ 이상 $u$ 이하의 자연수 중 등차수열 $A$나 등비수열 $G$에 속하는 수의 개수를 출력한다.

$a = 452$, $b = 24$, $c = 4$, $d = 5$, $u = 600$인 경우 조건을 만족하는 수는 $4$, $20$, $100$, $452$, $476$, $500$, $524$, $548$, $572$, $596$이다.