https://www.luogu.org/problemnew/show/T14200 题目描述 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]中，存在多少有意义的数字。 输入输出格式 输入格式： 第一行3个数分别表示L,R,p。 输出格式： 一个数表示答案。 输入输出样例 输入样例#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。
这个题目的暴力很好写，开个桶，90%的数据就过了。有机会要重新造个数据。当数据范围到5e8的时候，我们要所有可能的数。因为题目总步数限制50步，那么进行多次加或乘得到的数的总数并不特别多，打表看看，不会证明。因为b只能进行加一操作，要得到一个较大数的时候就需要来乘b,要得到一个a,一定是通过乘法得到的。虽然得到这个数的途径很多，但一个数能否得到我们可以通过唯一分解来判定。因次，我们找出50步范围内的所有素数，在R要求的范围内统计。统计通过dfs来完成，要不重复的计数，我们从大的质数开始，不断乘自己，越界了就去乘更小的数。这样找出不限制步数能找到的所有可能生成的数。排序待用。这样找到的数不一定是最优步数，比如42=7*3*2得到的，需要7+3=10步，而最优是7*6，需要7+2=9步。
然后判断p步能否达到，在走*i的情况下，如果b[k]*i能得到b[j],则b[j]=min(b[k]+1) 参考代码：当然是抄std了，不过的按照自己的理解重新写了下。
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; long long cnt,i,a[105],b[3000005],o,j,dp[3000005],l,r,p,k,sum; bool FLAG,v[3000005]; void dfs(long long y,long long z) { b[++cnt]=y; if(y*a[z]<=r)dfs(y*a[z],z); for (int i=z-1;i>0;i--) if(y*a[i]<=r)dfs(y*a[i],i); } int main() { scanf("%lld%lld%lld",&l,&r,&p); for (i=2; i<=50; i++) { FLAG=true; for (j=2; j<i; j++) if (i%j==0) FLAG=false; if (FLAG) a[++o]=i; } dfs(1,o); sort(b+1,b+cnt+1); for (i=2; i<=cnt; i++) dp[i]=105;//dp[1]=0; for (i=2; i<=p; i++) {//p,步数 j=1; for( k=1;b[k]*i<=b[cnt];k++){ while(i*b[k]>b[j])j++; // cout<<" w"<<i<<" "<<j<<" "<<k<<" dp"<<b[k]<<" "<<b[j]<<endl; if(b[k]*i==b[j]) { if (dp[k]+1<dp[j]) dp[j]=dp[k]+1; // cout<<i<<" "<<j<<" "<<k<<" dp"<<dp[k]<<" "<<dp[j]<<endl; if (dp[j]+i<=p) v[j]=1; j++; } } /* k=1; for (j=1; j<=cnt; j++) if (b[j] % i==0) {//怎样用最少的步数得到这些数呢 if (dp[k]+1<dp[j]) dp[j]=dp[k]+1; k++; if (dp[j]+i<=p) v[j]=1; } */ } v[1]=1; for (i=1; i<=cnt; i++) if (b[i]>=l && v[i]) sum++; cout<<sum; return 0; }
