问题2134--第n个丑数(ugly)

2134: 第n个丑数(ugly)

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

给定三个素数p1, p2, p3，一个整数如果其素因子仅由p1或p2或p3构成，我们称之为{p1, p2, p3}丑数。
{p1, p2, p3}丑数序列指的是所有{p1, p2, p3}丑数按照从小到大的顺序组成的序列，表示为H{p1, p2, p3}。例如H{2, 3, 5}=2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, ...
BSNY现在给定p1, p2, p3，问你H{p1, p2, p3}中，第n个{p1, p2, p3}丑数是多少？例如第5个{2, 3, 5}丑数为6。

输入

输入p1, p2, p3, n

输出

输出答案 (输入和输出数据保证在10^18以内)

样例输入 Copy 

7 13 19 100

样例输出 Copy 

26590291

提示

30%数据    1<=n<=100
60%数据    1<=n<=1000
100%数据   1<=n<=10000

来源/分类

丑数 构造算法 难度6 
[提交] [状态]