AtCoder-abc250_d 250-like Number

250-like Number

\(k = p * q ^ 3\) 且有 \(p < q\) 且 \(q\) 和 \(p\) 都是素数，问在 \([1,n]\) 中有多少个 \(k\)

二分 素数筛

这个题比较有趣

首先素数的话先用一个欧拉筛预处理一下

接着要寻找合理的情况，本来是想用 \(O(n^2)\) 强行莽一下，但是一直死活写不对，就突然想到二分，一下就过了

因为 \(k = p * q ^ 3\) 且有 \(p < q\)，所以可以枚举 \(q\)，然后再找有多少个符合的 \(p\)

而找 \(p\) 的数量，可以直接用二分去寻找第一个大到不符合要求的 \(p\) 的位置，然后知道有多少个 \(p\) 符合条件

这题比较友好的一点是，因为查询的是素数乘积，所以不会出现说相同一个数字有多种分解的情况，就不用查重，不然还得用一个 set 去维护

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e6 + 10;
int prime[maxn], tp = 0;
long long p[maxn];

void init()
{
    int n = 1e6 + 1;
    for(int i=2; i> n;
    for(int i=0; i