Arithmetic and Geometric Sequences

Time limit2sMemory limit512 MB

Summary

Count integers from 1 to u that lie in an arithmetic sequence or a geometric sequence, counting overlaps only once.

Level: Medium5 of 10
Topics: Math, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

The arithmetic sequence $A$ has general term $a + b \times x$ and the geometric sequence $G$ has general term $c \times d^y$ , where $x$ and $y$ are non-negative integers.

Given $a$ , $b$ , $c$ , $d$ , and $u$ , write a program that counts the integers from $1$ to $u$ that belong to $A$ or to $G$ . A number that belongs to both sequences is counted as well. If the same number appears several times in a sequence, it still counts once.

Input

The first line contains $a$ , $b$ , $c$ , $d$ , and $u$ , separated by spaces. ( $1 \le a, b, c, u \le 10^{12}$ , $1 \le d \le 10^5$ )

Output

Print on the first line how many integers between $1$ and $u$ inclusive belong to the arithmetic sequence $A$ or to the geometric sequence $G$ .

Note

For $a = 452$ , $b = 24$ , $c = 4$ , $d = 5$ , and $u = 600$ , the numbers that satisfy the condition are $4$ , $20$ , $100$ , $452$ , $476$ , $500$ , $524$ , $548$ , $572$ , $596$ .

Examples4

Example 1
Input
```
1 1 1 2 1000
```
Expected output
```
1000
```
Example 2
Input
```
3 3 1 2 1000
```
Expected output
```
343
```
Example 3
Input
```
40 77 40 100000 40
```
Expected output
```
1
```
Example 4
Input
```
452 24 4 5 600
```
Expected output
```
10
```