HDU 3199 Hamming Problem
Hamming Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1305 Accepted Submission(s): 583
Problem Description
For each three prime numbers p1, p2 and p3, let's define Hamming sequence Hi(p1, p2, p3), i=1, ... as containing in increasing order all the natural numbers whose only prime divisors are p1, p2 or p3.
For example, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, ...
So H5(2, 3, 5)=6.
Input
In the single line of input file there are space-separated integers p1 p2 p3 i.
Output
The output file must contain the single integer - Hi(p1, p2, p3). All numbers in input and output are less than 10^18.
Sample Input
7 13 19 100
Sample Output
26590291
Source
Northeastern Europe 2000 - Far-Eastern Subregion
解析:本题是[HDU 1058 Humble Numbers](http://www.cnblogs.com/inmoonlight/p/6030949.html)的升级版,2、3、5变成了p1、p2、p3。不过原理是相同的,都是运用DP的思想。因为题目有说明所有输入输出小于10^18,我们可以用2、3、5来得到最大可能出现的下标。经过测试,第一个大于或等于10^18的数下标为10916,因而数组的大小最小为10917。
```
#include
#include
#define ll long long
using namespace std;
ll res[11000];
void solve(int a, int b, int c, int n)
{
res[0] = 1;
int p1 = 0, p2 = 0, p3 = 0;
for(int i = 1; i <= n; ++i){
res[i] = min(res[p1]a, min(res[p2]b, res[p3]c));
if(res[i] == res[p1]a) ++p1;
if(res[i] == res[p2]b) ++p2;
if(res[i] == res[p3]c) ++p3;
}
printf("%I64d\n", res[n]);
}
int main()
{
int a, b, c, n;
while(~scanf("%d%d%d%d", &a, &b, &c, &n)){
solve(a, b, c, n);
}
return 0;
}
最新文章
- 基于struts2和hibernate的分页实现
- JavaScript判断各浏览器CSS前缀的两种方式
- ubuntu14升级到15后遇到的问题
- HttpWebResponse返回信息
- sql2008 附加数据库出错解决方法
- C#使用指针表达式
- 51Nod 1405 树的距离之和 (树dp)
- 【转】用perl写的单位电脑信息采集程序
- C# Generic(转载)
- 查看linux内存、cpu
- jquery之获取当前时间
- respondsToSelector的使用
- Linux 经常使用 性能 检测 命令 说明
- 树莓派小车By 树莓派爱好者ITJoker(通过python socket通信实现树莓派视频小车)(一)
- luogu P1659 [国家集训队]拉拉队排练
- go中的读写锁RWMutex
- [ZZ]Appium 文档翻译
- HTTP 无法注册URL 进程不具有命名空间的访问权限
- DB2自增长ID
- 安装caffe(opencv3+anaconda3)