题目描述

给定一个等差数列，第一项是 a，从第二项开始，每项与前一项的差都是一个定值 b。如果用数学形式来表示，那么可以表示成 a + b × x，其中 x≥0，且是整数。例如：a=1，b=2，那么这个等差数列就是：1, 3, 5, 7, 9…

再给定一个等比数列，第一项是 c，从第二项开始，每项是前一项的 d 倍。如果用数学形式来表示，那么可以表示成 c × (d^y)，其中 y≥0，且是整数。例如：c=2，d=3，那么这个等比数列就是：2, 6, 18, 54…

你的任务是计算在 1 至 upperBound 内的正整数，有多少正整数是“合法”的？

所谓的“合法”是指：该整数属于上面给定的等差数列的某项或者属于等比数列的某项，或者既属于等差数列的项也属于等比数列的项。

输入格式

一行，5 个整数，分别是 a, b, c, d, upperBound。

（1≤a,b,c,upperBound≤10¹²，1≤d≤10¹⁸）

对于 80% 的数据，1≤upperBound≤1000000。

输出格式

一个整数，表示“合法”正整数的个数。

1 1 1 2 1000

1000

</p>

提示

第 1 组样例产生的等差数列是 1, 2, 3, 4, …，产生的等比数列是 1, 2, 4, 8, …，所以【1，1000】范围内所有正整数都是“合法”的。

第 3 组样例“合法”的 10 个数分别是：4, 20, 100, 452, 476, 500, 524, 548, 572, 596。

输入：
3 3 1 2 1000
输出：
343

输入：
452 24 4 5 600
输出：
10

来源

枚举优化