简答题 偏难
#21375

B-smooth 数 题面描述 小杨同学想寻找一种名为B-smooth 数的正整数。 如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。 小…

B-smooth 数

题面描述

小杨同学想寻找一种名为B-smooth 数的正整数。

如果一个正整数的最大质因子不超过B,则该正整数为B-smooth 数。

小杨同学想知道,对于给定的n和B,有多少个不超过n的B-smooth 数。

输入格式

第一行包含两个正整数n,B,含义如题面所示。

输出格式

输出一个非负整数,表示不超过n的B-smooth 数的数量。


样例输入

10 3

样例输出

7

样例解释

在不超过10的正整数中,3-smooth 数有{1,2,3,4,6,8,9},共7个。

数据范围

对于全部数据,保证有1≤n≤106,1≤B≤106。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; int main() { int n, B; cin &gt;&gt; n &gt;&gt; B; assert(1 &lt;= n &amp;&amp; n &lt;= 1e6); assert(1 &lt;= B &amp;&amp; B &lt;= 1e6); vector&lt;bool&gt; vis = vector&lt;bool&gt;(n + 5, false); vector&lt;int&gt; mx_prime_factor = vector&lt;int&gt;(n + 5, 0); vector&lt;int&gt; prime; mx_prime_factor[1] = 1; for (int i = 2; i &lt;= n; i ++) { if (! vis[i]) { mx_prime_factor[i] = i; prime.push_back(i); } for (int p : prime) { if (1ll * p * i &gt; n) break ; vis[i * p] = 1; mx_prime_factor[i * p] = max(mx_prime_factor[i * p],max(mx_prime_factor[i], p)); if (i % p == 0) break ; } } int ans = 0; for (int i = 1; i &lt;= n; i ++) ans += (mx_prime_factor[i] &lt;= B); cout &lt;&lt; ans; return 0; }</pre>
这道题暂未补解析。