hdu4028 The time of a day[map优化dp]
2024-08-24 15:20:09
The time of a day
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1297 Accepted Submission(s): 594
Problem Description
There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every pointer ticks once per second, and the i-th pointer move to the starting position after i times of ticks. The wise of the byte island decide to define a day as the time interval between the initial time and the first time when all the pointers moves to the position exactly the same as the initial time.
The wise of the island decide to choose some of the N pointers to make the length of the day greater or equal to M. They want to know how many different ways there are to make it possible.
The wise of the island decide to choose some of the N pointers to make the length of the day greater or equal to M. They want to know how many different ways there are to make it possible.
Input
There are a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases.
For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263-1)
For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263-1)
Output
For each test case, output a single integer denoting the number of ways.
Sample Input
3
5 5
10 1
10 128
5 5
10 1
10 128
Sample Output
Case #1: 22
Case #2: 1023
Case #3: 586
Case #2: 1023
Case #3: 586
Source
Recommend
#include<map>
#include<cstdio>
using namespace std;
typedef long long ll;
map<ll,ll>f[];ll m,ans;int n,cas,Cas;
map<ll,ll>::iterator it,ii;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int main(){
f[][]=;
for(int i=;i<=;i++){
f[i]=f[i-];
f[i][i]++;
for(it=f[i-].begin();it!=f[i-].end();it++){
f[i][lcm(it->first,i)]+=it->second;
}
}
for(scanf("%d",&Cas),cas=;cas<=Cas;cas++){
scanf("%d%I64d",&n,&m);printf("Case #%d: ",cas);
ans=;
for(it=f[n].begin();it!=f[n].end();it++){
if(it->first>=m) ans+=it->second;
}
printf("%I64d\n",ans);
}
return ;
}
最新文章
- CALayer笔记
- [js]识别浏览器及版本
- 黑马程序员——JAVA基础之主函数main和静态static,静态代码块
- mysql 查询重复值命令
- KDE子项目一览 good
- PostgreSQL的存储系统二:REDOLOG文件存储结构二
- WEB打印的几种方案
- windows下使用lighttpd+php(fastcgi)+mysql
- 使用node.js编写脚本将JSON数据转换为SQL语句
- hdu_1014(竟然真的还有更水的)
- nginx学习之rewrite
- ●BZOJ 1076 [SCOI2008]奖励关
- Python实现猜数字游戏1.0版
- Beta冲刺(1/7)
- ubuntu编译安装opencv
- linux ubuntu 关于vim得一些基本命令
- [CF1131C]Birthday【贪心】
- vue2.0项目实战(3)使用axios发送请求
- Super expression must either be null or a function, not undefined
- Beta冲刺 (7/7)