题面翻译
二元组$ (a,b)\(,可以变成\) (a,b+1)\(或\) (ab,b)$
你有初始二元组$ (1,0)\(,给你区间\) [l,r]\(,和一个整数\) p\(,在区间内选一个数\) x\(,使\) (1,0)\(在不超过\) p\(步变化后,第一维的值变成\) x\(,求\) x\(的个数\) (2<=l<=r<=10^{9},1<=p<=100) $。
题解
注意到第二维最大值为 \(p\) ，因此我们最终得到的答案的最大质因子不超过 \(p\)。
当 \(p=100\) 时搜一下发现在 \([1,10^9]\) 范围内可能成为答案的数的个数不超过 \(3*10^6\) 个，开个 \(num\) 数组将其记录下来，记得对 \(num\) 数组排序，保证其有序，这样后面转移的时候才能保证复杂度。
算步数可以 \(dp\) ，设 \(ste\_p_i\) 表示凑出 \(num_i\) 的最小步数，\(can\__i\) 表示 \(num_i\) 是否能被凑出。
外层枚举二元组 \(b\) 的值 \(second\_val\)，转移是容易有的： \(ste\_p_i=min(ste\_p_i,ste\_p_k+1)(num_k*second\_val=num_i)\)。
代码
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
const int N=3000010;
const int inf=2000000000;
typedef long long ll;
using namespace std;
int cnt,tot,l,r,p,ans;
int prime[30],num[N],ste_p[N];
bool can_[N];
void get_prime()
{
cnt=0;
For(i,2,p)
{
int lim=sqrt(i);
bool flag=true;
For(j,2,lim)
{
if((i%j)==0)
{
flag=false;
break;
}
}
if(flag==true)
{
++cnt;
prime[cnt]=i;
}
}
return;
}
void dfs(ll x,int pos)
{
if(pos>cnt)
return;
ll tmp=x;
while(1)
{
dfs(tmp,(pos+1));
tmp*=prime[pos];
if(tmp>r)
break;
++tot;
num[tot]=tmp;
}
return;
}
int main()
{
scanf("%d%d%d",&l,&r,&p);
tot=1;
num[1]=1;
get_prime();
dfs(1,1);
tot=(unique(num+1,num+tot+1)-num-1);
sort(num+1,num+tot+1);
ste_p[1]=0;
can_[1]=true;
For(i,2,tot)
ste_p[i]=inf;
For(second_val,2,p)
{
int first_val=second_val;
For(k,1,tot)
{
while((first_val<=tot) && (num[first_val]!=(num[k]*second_val)))
++first_val;
if(first_val>tot)
break;
ste_p[first_val]=min(ste_p[first_val],(ste_p[k]+1));
if((num[first_val]<l) || (can_[first_val]==true))
continue;
if((ste_p[first_val]+second_val)<=p)
can_[first_val]=true;
}
}
ans=0;
For(i,2,tot)
{
if(can_[i]==true)
++ans;
}
printf("%d",ans);
return 0;
}