牛客挑战44C: 有用的数

题意

定义前缀 为 且一个数 对其前缀 有贡献当且仅当
特别的， 不视为对其前缀 有贡献
现在你需要求出 内所有对其前缀 有贡献的数的个数

分析

考虑一个数怎么样才会对前缀 造成影响
会发现这个数一定会是素数幂，就是说，当一个数可以表示为 ，那么
所以，这道题就转化为了在 中有多少个素数幂
进一步考虑：

• 当 时， 素数 的贡献为
• 当 时，素数 的贡献为

所以在根号范围内的答案是可以线性筛硬算的，那么在根号范围外的就是求素数个数的问题了
那么我们来聊一聊这个根号外的素数个数该怎么求呢
首先，声明几个记号：

• 表示第 个素数
• 表示 范围内的素数个数
• 表示不大于 且不能整除任何一个 的自然数个数

那么显然有：

给定一个自然数 ，如果 ，那么有：

这个方法大概可以计算 数量级的素数个数
但是有一种更快的处理方式，对于实数 ，和自然数 和 , 定义 表示不大于 ，且恰好有 个大于 的素因子的整数个数，更进一步，设定： ，那么有：

这个和 实际上只有有限个非零的项。设 为一个整数，使得 ，并设 。那么当 时， 且 。因此有：

的计算方式可以用这种方法来获得：

这样，我们就可以在 的时间复杂度内完成 的素数个数的计算
然后就可以用线性筛求出根号内的素数幂 的贡献 (c=1的贡献在上一步中已经计算过了)，加在一起即可

Code

#include <cstdio>
#include <cmath>

typedef long long ll;
const int maxn = 1e5 + 10;
const int maxm = 105;

namespace prime
{
    ll phi[maxn][maxm];
    int p[maxn], pi[maxn * 10], cnt;
    bool vis[maxn * 10];

    inline void init()
    {
        for (int i = 2; i < maxn * 10; ++i) {
            if (!vis[i]) p[++cnt] = i;
            pi[i] = cnt;
            for (int j = 1; j <= cnt && i * p[j] < maxn * 10; ++j) {
                vis[i * p[j]] = 1;
                if (i % p[j] == 0) break;
            }
        }

        for (int n = 0; n < maxm; ++n)
            for (int m = 0; m < maxn; ++m)
                if (!n) phi[m][n] = m;
                else phi[m][n] = phi[m][n - 1] - phi[m / p[n]][n - 1];
    }

    inline ll Phi(ll m, int n)
    {
        if (n == 0) return m;
        else if (p[n] >= m) return 1;
        else if (m < maxn && n < maxm) return phi[m][n];
        return Phi(m, n - 1) - Phi(m / p[n], n - 1);
    }

    inline ll Pi(ll m)
    {
        if (m < maxn) return pi[m];
        int s = sqrt(m), y = cbrt(m), n = pi[y];
        ll res = Phi(m, n) + n - 1;
        for (int i = n + 1; p[i] <= s; ++i) res -= Pi(m / p[i]) - Pi(p[i]) + 1;
        return res;
    }
}

ll n, res;
int p[maxn * 10], cnt, ntc;
bool vis[maxn * 10];

inline void SK()
{
    scanf ("%lld", &n);
    res = prime::Pi(n);
    ll maxn = sqrt(n);
    cnt = 0;
    for (int i = 2; i <= maxn; ++i) {
        if (!vis[i]) {
            p[++cnt] = i;
            ll temp = 1ll * i * i;
            while (temp <= n) {
                ++ntc;
                temp *= i;
            }
        }
        for (int j = 1; j <= cnt && i * p[j] <= maxn; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }

    }
}

int main()
{
    prime::init();
    SK();
    printf ("%lld\n", res + ntc);
}

参考资料：
wikipedia