2020杭电第六场第八题题解

用$mx_x$表示$x$的最大质因数，$mn_x$表示$x$的最小质因数，$f(x)$表示小于等于$x$的最大质数，$g(x)$表示小于$x$的最大质数，$h(x)$表示大于$x$的最小质数。

注意$mx_1=-\infty$，$mn_1=\infty$，$f(2^-)=-\infty$，$g(2)=-\infty$

$$\sum_{i=1}^n[mx_i\leq k]=\sum_{i=1}^n\prod_{p\in P\cap [k+1,n]}(1-[p|i]) \\=\sum_{i=1}^n\sum_{T\subset P\cap[k+1,n]}(-1)^{|T|}\prod_{p\in T}[p|i] \\=\sum_{i=1}^n\sum_{x=1}^n[mn_x>k]\mu(x)[x|i] \\=\sum_{x=1}^n[mn_x>k]\mu(x)\left\lfloor\frac{n}{x}\right\rfloor$$
故实际要对所有$s=\left\lfloor\frac{n}{*}\right\rfloor$求出 $$\sum_{x=1}^s[mn_x>k]\mu(x).$$
$$\sum_{x=1}^s[mn_x>k]\mu(x)=\sum_{x=1}^s\mu(x)\prod_{p\in P\cap[1,k]}(1-[p|x]) \\=\sum_{x=1}^s\mu(x)(1-[f(k)|x])\prod_{p\in P\cap[1,f(k)-1]}(1-[p|x]) \\=\sum_{x=1}^s[mn_x>f(k)-1]\mu(x)-\sum_{x=1}^s[mn_x>f(k)-1][f(k)|x]\mu(x) \\=\sum_{x=1}^s[mn_x>f(k)-1]\mu(x)-\sum_{x=1}^{\left\lfloor\frac{s}{f(k)}\right\rfloor}[mn_{xf(k)}>f(k)-1]\mu(xf(k)) \\=\sum_{x=1}^s[mn_x>f(k)-1]\mu(x)+\sum_{x=1}^{\left\lfloor\frac{s}{f(k)}\right\rfloor}[mn_x>f(k)-1]\mu(x)(1-[f(k)|x]) \\=\sum_{\alpha=0}^\infty\sum_{x=1}^{\left\lfloor\frac{s}{f(k)^\alpha}\right\rfloor}[mn_x>f(k)-1]\mu(x) \\=\sum_{x=1}^{\left\lfloor\frac{s}{f(k)}\right\rfloor}[mn_x>k]\mu(x)+\sum_{x=1}^s[mn_x>f(k)-1]\mu(x)$$
倒过来就是 $$\sum_{x=1}^s[mn_x>f(k)-1]\mu(x)=\sum_{x=1}^s[mn_x>k]\mu(x)-\sum_{x=1}^{\left\lfloor\frac{s}{f(k)}\right\rfloor}[mn_x>k]\mu(x).$$
于是可以将$f(k)$从大到小递推求值，起始条件如下：
$$\sum_{x=1}^s[mn_x>s]\mu(x)=1,\sum_{x=1}^s[mn_x>f(\sqrt{s})]\mu(x)=1-\sum_{x=h(\sqrt s)}^s[x\in P]$$
于是任务变为对所有形如$\left\lfloor\frac{n}{*}\right\rfloor$的$s$，以及$s=k$求出 $$\sum_{x=1}^s[x\in P]=\sum_{x=2}^s[x\in P\lor mn_x\geq s+1]$$
而（下文中$2\leq g(k)\leq s$） $$\sum_{x=2}^s[x\in P\lor mn_x\geq k]=\sum_{x=2}^s[x\in P\lor mn_x\geq g(k)]-\sum_{x=1}^s[mn_x=g(k)]+1\\=\sum_{x=2}^s[x\in P\lor mn_x\geq g(k)]+1-\sum_{x=1}^{\left\lfloor\frac{s}{g(k)}\right\rfloor}[mn_x\geq g(k)] \\=\sum_{x=2}^s[x\in P\lor mn_x\geq g(k)]-\sum_{x=2}^{\left\lfloor\frac{s}{g(k)}\right\rfloor}[x\in P\lor mn_x\geq g(k)]+\sum_{x=2}^{g(k)-1}[x\in P].$$
对于$g(k)^2\leq s$（上式中最后一个等号仅对此情况成立）递推即可，而$g(k)^2>s$时，上式中$1-\sum_{x=1}^{\left\lfloor\frac{s}{g(k)}\right\rfloor}[mn_x\geq g(k)]=0$所以不再变化。

#include <bits/stdc++.h>
namespace fast_pool {
    constexpr size_t const size = 481 << 20;
    unsigned char data[size];
    unsigned char* ptr = data;
    void clear() {ptr = data;}
    void* fast_alloc(size_t n) {ptr += n; return ptr - n;}
};
template<class T>
class myallocator {
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef value_type const* const_pointer;
    typedef value_type const& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    pointer allocate(size_t n, const T* pHint = 0) {
        return (pointer)(fast_pool::fast_alloc(n * sizeof(T)));
    }
    void deallocate(pointer p, size_type n) {}
    void destroy(T* p) {p->~T();}
    void construct(T* p, const T& val) {::new((void *)p) T(val);}
    size_t max_size() const throw() {
        return (fast_pool::size + fast_pool::data - fast_pool::ptr) / sizeof(T);
    }
    T* address(T& val) const {return &val;}
    const T* address(const T& val) const {return &val;}
    myallocator() throw() {}
    myallocator(const T* p) throw() {}
    ~myallocator() throw() {}
    template <typename _other> struct rebind { typedef myallocator<_other> other; };
};
std::stringstream iss;
std::stringstream oss;
std::string instr;
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
const ul maxn = 1e9;
const ul maxsqrtn = 31622;
const ul maxd = maxsqrtn;
ul T;
ul n, k;
ul nid1[maxsqrtn + 1];
ul nid2[maxsqrtn + 1];
ul nv[maxsqrtn + maxsqrtn + 1];
ul sqrtnv[maxsqrtn + maxsqrtn + 1];
std::vector<ul, myallocator<ul>> ans2[maxsqrtn + maxsqrtn + 1];
ul nc;
void initid(ul n, ul id1[], ul id2[], ul v[], ul& c)
{
    for (ul l = 1, r, i = 1; l <= n; l = r + 1, ++i) {
        ul nq = n / l;
        r = n / nq;
        if (nq <= r) {
            id2[nq] = i;
        }
        if (r <= nq) {
            id1[r] = i;
        }
        v[i] = r;
        c = i;
    }
}
ul getid(ul x, ul n, const ul id1[], const ul id2[])
{
    return ull(x) * x <= n ? id1[x] : id2[n / x];
}
std::vector<ul, myallocator<ul>> prime(maxd);
std::vector<ul, myallocator<ul>> fprime(maxd);
std::vector<bool> notprime(maxd + 1);
ul alcntprime[maxsqrtn + 1];
ul ncntprime[maxsqrtn + maxsqrtn + 1];
ul kp;
void initcntprime(ul n, const ul id1[], const ul id2[], const ul v[], ul c, ul cntprime[])
{
    for (ul i = 1; i <= c; ++i) {
        cntprime[i] = v[i] - 1;
    }
    for (ul gk : prime) {
        if (gk * gk > n) {
            break;
        }
        for (ul i = c; i >= 2 && v[i] >= gk * gk; --i) {
            cntprime[i] -= cntprime[getid(v[i] / gk, n, id1, id2)];
            cntprime[i] += alcntprime[gk - 1];
        }
    }
}
ul finalans2[maxsqrtn + maxsqrtn + 1];
void initans2()
{
    for (ul i = 1; i <= nc; ++i) {
        ans2[i][alcntprime[sqrtnv[i]]] = 1 - ncntprime[i] + alcntprime[sqrtnv[i]];
        for (ul j = alcntprime[sqrtnv[i]]; j >= 1 && j >= kp + 1; --j) {
            ul ii = getid(nv[i] / fprime[j], n, nid1, nid2);
            if (j <= alcntprime[sqrtnv[ii]]) {
                ans2[i][j - 1] = ans2[i][j] - ans2[ii][j];
            } else if (j <= ncntprime[ii]) {
                ans2[i][j - 1] = ans2[i][j] - (j - ncntprime[ii] + 1);
            } else {
                ans2[i][j - 1] = ans2[i][j] - 1;
            }
        }
        if (kp <= alcntprime[sqrtnv[i]]) {
            finalans2[i] = ans2[i][kp];
        } else if (kp <= ncntprime[i]) {
            finalans2[i] = kp - ncntprime[i] + 1;
        } else {
            finalans2[i] = 1;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    iss.tie(0);
    oss.tie(0);
    std::getline(std::cin, instr, char(0));
    iss.str(instr);
    fprime.resize(0);
    fprime.push_back(1);
    prime.resize(0);
    for (ul i = 2; i <= maxd; ++i) {
        alcntprime[i] = alcntprime[i - 1];
        if (!notprime[i]) {
            fprime.push_back(i);
            prime.push_back(i);
            ++alcntprime[i];
        }
        for (ul p : prime) {
            if (p * i > maxd) {
                break;
            }
            notprime[p * i] = true;
            if (i % p == 0) {
                break;
            }
        }
    }
    iss >> T;
    for (ul Case = 1; Case <= T; ++Case) {
        iss >> n >> k;
        initid(k, nid1, nid2, nv, nc);
        initcntprime(k, nid1, nid2, nv, nc, ncntprime);
        kp = ncntprime[nc];
        initid(n, nid1, nid2, nv, nc);
        initcntprime(n, nid1, nid2, nv, nc, ncntprime);
        for (ul i = 1; i <= nc; ++i) {
            sqrtnv[i] = std::sqrt(nv[i]);
            while ((sqrtnv[i] + 1) * (sqrtnv[i] + 1) <= nv[i]) {
                ++sqrtnv[i];
            }
            ans2[i].resize(alcntprime[sqrtnv[i]] + 1);
        }
        initans2();
        ul ans = 0;
        for (ul i = 1; i <= nc; ++i) {
            ans += nv[nc + 1 - i] * finalans2[i];
            if (i != 1) {
                ans -= nv[nc + 1 - i] * finalans2[i - 1];
            }
        }
        oss << ans << '\n';
    }
    std::cout << oss.str();
    return 0;
}