牛客挑战44C: 有用的数

题意

定义前缀 $\mathbb{lcm}$ 为 $L_n= \mathbb{lcm}(1,2,3,...,n)$ 且一个数 $x$ 对其前缀 $\mathbb{lcm}$ 有贡献当且仅当 $L_{x-1}\not= L_x$
特别的， $1$ 不视为对其前缀 $\mathbb{lcm}$ 有贡献
现在你需要求出 $1\sim n$ 内所有对其前缀 $\mathbb{lcm}$ 有贡献的数的个数

分析

考虑一个数怎么样才会对前缀 $\mathbb{lcm}$ 造成影响
会发现这个数一定会是素数幂，就是说，当一个数可以表示为 ${p_i}^c\quad c\in[1,\infty)$ ，那么 $L_{{p_i}^c}=L_{{p_i}^c-1}\times p_i$
所以，这道题就转化为了在 $[1,n]$ 中有多少个素数幂
进一步考虑：

当 $p_i>\sqrt n$ 时，素数 $p_i$ 的贡献为 $1$
当 $p_i\le\sqrt n$ 时，素数 $p_i$ 的贡献为 $\log_{p_i}n$

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

$p_i$ 表示第 $i$ 个素数
$\pi(x)$ 表示 $[1,x]$ 范围内的素数个数
$\Phi(m,n)$ 表示不大于 $m$ 且不能整除任何一个 $p_i\quad i\in[1,n]$ 的自然数个数

那么显然有：

$\Phi(m,n)=\Phi(m-n-1)-\Phi(\frac m{p_i}, n-1)$
$\Phi(m,0)=\left\lfloor m\right\rfloor$

给定一个自然数 $m$ ，如果 $n=\pi(\sqrt[3]{m})\quad\mu=\pi(\sqrt m)-n$ ，那么有：

$\pi(m)=\Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu}2-1-\sum_{k=1}^\mu\pi\left(\frac m{p_{n+k}}\right)$

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

$\Phi(m,n)=\sum_{k\ge0}P_k(m,n)$

这个和实际上只有有限个非零的项。设 $y$ 为一个整数，使得 $\sqrt[3]m\le y\le\sqrt m$ ，并设 $n=\pi(y)$ 。那么当 $k \ge 3$ 时， $P_1(m,n)=\pi(m)-n$ 且 $P_k(m,n)=0$ 。因此有：

$\pi(m)=\Phi(m,n)+n-1-P_2(m,n)$

$P_2(m,n)$ 的计算方式可以用这种方法来获得：

$P_2(m,n)=\sum_{y<p\le \sqrt m}\left(\pi\left(\frac mp\right)-\pi(p)+1\right)$

这样，我们就可以在 $O(n^{\frac 23})$ 的时间复杂度内完成 $1\sim n$ 的素数个数的计算
然后就可以用线性筛求出根号内的素数幂 $p_i^c c\in(1,\infty)$ 的贡献 (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

牛客挑战44 有用的数

牛客挑战44C: 有用的数

题意

分析

Code