数字(number)
Time Limit:2000ms Memory Limit:128MB
题目描述
LYK定义了一个新的计算。
具体地，一开始它有两个数字a和b。
每一步，它可以将b增加1，或者将a乘上b。
也就是说(a,b)经过一次操作后可以变成(a,b+1)或者(a*b,b)。再经过一次操作可以变成(a,b+2)或者(a*(b+1),b+1)或者(a*b,b+1)或者(a*b*b,b)。接下来都类似……它认为只有在这个括号左侧的数字才是有意义的，并且它想执行的操作数不会很多。
具体的，如果LYK能通过不超过p步，使得这个括号内左侧的数字变成x，那么x就是一个有意义的数字！
但zhw觉得这个题目太难了，会为难大家，于是他将这个问题中初始的a定义为了1，把b定义为了0。
LYK想知道在一段区间[L,R]中，存在多少有意义的数字。
输入格式(number.in)
第一行3个数分别表示L,R,p。
输出格式(number.out)
一个数表示答案。
输入样例1
1 100 10
输出样例1
46
输入样例2
233 233333333 50
输出样例2
332969
数据范围
对于30%的数据L,R<=10。
对于另外20%的数据p<=20。
对于70%的数据1<=L<=R<=1000，1<=p<=50。
对于90%的数据1<=L<=R<=1000000，1<=p<=50。
对于100%的数据1<=L<=R<=500000000，1<=p<=50。（这一个点蒟蒻不会啦）
用搜索，加上一些剪枝就可以达到九十分了。
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
int L,R,p,ans;
bool f[1000009];
void dfs(int a,int b,int step)
{
if(a>R) return;
f[a]=1;
if(step==p) return;
dfs(a,b+1,step+1);
dfs(a*b,b,step+1);
}
int main()
{
scanf("%d%d%d",&L,&R,&p);
f[1]=1;
dfs(1,2,2);//！！省去无用的！！
for(int i=L;i<=R;i++)
if(f[i]) ans++;
printf("%d",ans);
return 0;
}