B光滑数

Description

B为一个正整数，如果一个自然数N的因子分解式中没有大于B的因子，我们就称N是一个B光滑数。请你编一个程序，求出某个区间中所有的B光滑数的个数。

Analysis

首先，打一个暴力，枚举n~n+m，找出每个数的最大质因子，不大于b就算上，输出答案。

不错，得了50分。

想到：b不一定是质数，所以要找到最接近b的质数。可以用欧拉线性筛。

接下来思考新的做法，递推递归是一个不错的选择。一开始我选择了尝试递推，发现：b光滑数一定包括b-1的光滑数，所以找到一个状态转移的方式：

B[i]=B[i-1]

上面说的并不准确，因为b-1不是质数，事实上b-1指的是b的前一个质数。

当然，状态转移不止这些，可以发现前n个数中的B光滑数除去B-1光滑数后只剩下B的倍数，而B的倍数除去所有B后一定是一个B-1光滑数，又可以得出：

B[a][b]=B[a][b-1]+B[a/b][b-1]+B[a/b/b][b-1]+...+B[1][b-1]

这个方程太长，能不能简化呢，可以。利用愤怒的小鸟（无限背包问题）思想可以发现，B[a/b][b]可能已经包含了b的n倍，所以只要由其转移而来即可。

B[a][b]=B[a][b-1]+B[a/b][b]

然而，直接递推完全存不下数组..所以放弃递推打起了递归。

思考一下边界问题：B[1][b]一定是1，B[a][1]也是1，对于B[a][b]当a<=b时，显然a个数都是b光滑数，所以边界已经确定好了。

85分！1WA2TLE，那么程序还存在问题，发现大量的状态重复运算，所以针对小规模数据进行记忆化(10000*3000)基本上足够。

95分！错了一个小点，应该是数据较大时想当然的处理在数据小时出现了错误，所以对于1000以内数据进行了暴力特判，过了。

Code 高于O(b·logbm)

#include 
#define ll long long
const ll N=1e6;
class B_Smooth_Number{private:int b;ll B[10001][3001];bool not_prime[N];std::vector  prime;void Euler(){for(ll i=2;ix){b=i-1;return;}}ll Query(ll x){return Search(x,b);}
}B;
int revolve(int x){int s=0;for(int i=2;i<=x;i++)while(!(x%i)){s=std::max(s,i);x/=i;}return s;
}
int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);ll n,m,b;scanf("%lld%lld%lld",&n,&m,&b);if(n+m<1000){int ans=0;for(int i=int(n);i<=int(n+m);i++)if(revolve(i)<=b)ans++;printf("%d\n",ans);return 0;}B.Update(b);printf("%lld\n",B.Query(m+n)-B.Query(n-1));return 0;
}

转载于:https://www.cnblogs.com/qswx/p/9509246.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！