本文主要是介绍B-smooth 数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过 B,则该正整数为 B-smooth 数。小杨同学想知道,对于给定的 n 和 B,有多少个不超过 n 的 B-smooth 数。
输入格式
第一行包含两个正整数 n 和 B,含义如题面所示。
输出格式
输出一个非负整数,表示不超过 n 的 B-smooth 数的数量。
输入输出样例
输入 #1
10 3
输出 #1
7
说明/提示
数据规模与约定
子任务 | 得分 | 𝑛≤n≤ | 𝐵B |
---|---|---|---|
1 | 30 | 10^3 | 1≤B≤10^3 |
2 | 30 | 10^6 | sqrt(n)≤B≤10^6 |
3 | 40 | 10^6 | 1≤B≤10^6 |
对全部的测试数据,保证 1≤n,B≤10^6。
做法一:线性
#include <iostream>
#include <vector>
using namespace std;vector<int>p;
int n,b;
bool c[1000010],v[1000010];
void init()
{for(int i=2;i<=1000000;i++){if(!c[i]){p.push_back(i);if(i>b)v[i]=true;}for(auto e:p){int t=i*e;if(t>1000000)break;c[t]=true;if(v[i]||v[e])v[t]=true;if(i%e==0)break;}}
}
int main()
{cin>>n>>b;init();int cnt=n;for(int i=1;i<=n;i++)cnt-=v[i];cout<<cnt;return 0;
}
关键词:逆向思维,边筛边算
逆向思维:题目要求的是B-smooth数,我们可以求出非B-smooth数,用n减去这个数量。B-smooth数的定义是最大质因子不超过b,隐含了任何质因子都不超过b,于是非B-smooth数就是有至少一个质因子大于b就够了。
边筛边算:利用筛法特性记录信息。v记录了i是否是非B-smooth数。
---------------------------------------------------------------------------------------------------------------------------------
做法二:埃氏
#include <iostream>
using namespace std;const int m=1000000;
int c[m];
void init()
{for(int i=2;i<=m;i++){if(c[i]==0){c[i]=i;for(int j=2;j<=m;j++){long long t=1ll*i*j;if(t>m)break;c[t]=i;}}}
}
int main()
{init();int n,b;cin>>n>>b;int cnt=0;for(int i=1;i<=n;i++)if(c[i]<=b)cnt++;cout<<cnt;return 0;
}
关键词:夹带私货,适当调整
夹带私货:将原本用于判断i是否是合数,此处我们可以将它改为int类型,用于记录i的最大质因子。这也是由于埃氏筛法的一个性质,每一个数都会被他所有的质因子筛一遍(正版不是这样,后面会说到),所以经过覆盖,c数组中存的数就成了i的最大质因子。
适当调整:正版的埃氏筛不是这样的,第二层循环本应从i开始。虽然这样做效率会高一些,但效率高的原因是每个数只被最小质因子筛了,c数组里存的就成了最小质因子,所以需要省去这个优化才能得出正确结果。
其他:当实在查不出错是重写一遍,要么写着写着发现问题,要么写完就过了……真的!
这篇关于B-smooth 数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!