AT_jag2017autumn_c Prime-Factor Prime 题解

题目链接：C - Prime-Factor Prime

题意：

设正整数 \(x\) 的质因数分解式为 \(x=\prod_{i=1}^k p_i^{\alpha_i}\) 。定义 \(f(x)=\sum_{i=1}^k \alpha_i\) 。

给出 \(l, r\) ，求对所有 \(i \in[l, r]\) ，有多少 \(f(i)\) 是质数。

\(1 \leq l \leq r \leq 10^9,~ 0 \leq r-l<10^6\) 。

注意到 \(r - l < 10^6\) ，但是直接枚举然后暴力拆的复杂度过于高了。

容易发现一个数的质因数个数最多有 \(\log_2 x\) 个，则若从质因数的角度出发可以节省很多时间。

套路地，筛出 \(2\) 到 \(\sqrt{10^9}\) 的所有质数，然后对于每个质数暴力计算贡献。

时间复杂度 \(\mathcal{O}((r - l) \log r)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define SqN ((int)(32015))

int l,r,res,f[N],val[N]; char vis[SqN];
void init(int len)
{
    vis[0] = vis[1] = 1;
    for(int i = l; i <= r; i++) val[i - l] = i;
    for(int i = 2; i <= len; i++)
    {
        if(vis[i]) continue;
        for(int j = i; j * i <= len; j++) vis[i * j] = true;
        for(int j = (l - 1) / i + 1; j * i <= r; j++)
            for(; val[i * j - l] % i == 0; val[i * j - l] /= i, ++f[i * j - l]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> l >> r; init(31645);
    for(int i = l; i <= r; i++)
    {
        if(val[i - l] > 1) ++f[i - l];
        if(!vis[f[i - l]]) ++ res;
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/problem/solution/AT_jag2017autumn_c