Codeforces665F

Codeforces665F题解

题意：

• 让你求出满足$x \leq n$且$d(x)=\sum_{d|x}=4$的$x$的个数。
• $n \leq 10^{11}$

题解：

• $x=\prod_{i=1}^{k} p_i^{a_i},d(x)=\prod_{i=1}^{k}a_i+1$
• $d(x)=4$
• 可以得到：
• $$\left\{\begin{aligned}k=1\\a_1=3\end{aligned}\right.or\ \left\{\begin{aligned}k=2\\a_1=1\\a_2=1\end{aligned}\right.$$
• 前者非常好统计，后者如果算上完全平方数，就相当于等于两素数乘积的数的个数，设为$Ans$。
• 考虑枚举小于等于$\sqrt{n}$的素数。
• $$Ans=\sum_{p_i \leq \sqrt{n}}f(\lfloor \frac{n}{p_i} \rfloor)-f(p_i)$$
• 其中$f(x)$表示小于等于$x$的素数个数。
• 然后我们听说一个叫做洲阁筛的东西。它的第一部分就是在求这个东西的。
• 于是借此机会学习了一下。
• 设$g_k(i,j)$表示$1 \cdots j$中与前$i$个质数均互质的数的$k$次方和。
• $$g_k(i,j)=g_k(i-1,j)-p_i^kg_k(i-1,\lfloor \frac{j}{p_i}\rfloor)$$
• 那么在求$f(p_i)$时，可以直接线性筛得到。
• 而$f(\lfloor \frac{n}{p_i} \rfloor)=g_0(m,n)+m$
• $m$表示小于等于$\sqrt{n}$的质数个数。
• 因为$j$的取值只有$O(\sqrt{n})$种，所以暴力复杂度$O(\frac{n}{logn})$。
• 然而如果$p_i^2>j$时：
• $$g_k(i,j)=g_k(i-1,j)-p_i^k$$
• 所以可以对于$p_{i_0}^{2}>j$时开始便不再转换。若需要$g_k(i_1,j)$的值，$i_1>=i_0$，就通过$g_k(i_1.j)=g_k(i_0,j)-\sum_{i=i_0+1}^{i_1}p_i^k$计算得到。
• 时间复杂度分析：
• $$\sum_{i=1}^{\sqrt{n}}O(\frac{\sqrt{i}}{logi})+\sum_{i=1}^{\sqrt{n}}O(\frac{\sqrt{\frac{n}{i}}}{log\sqrt{\frac{n}{i}}}) \approx \sum_{i=1}^{\sqrt{n}}O(\frac{\sqrt{\frac{n}{i}}}{log\sqrt{\frac{n}{i}}}) \\ \approx O(\frac{\sqrt{\int_{0}^{\sqrt{n}}\frac{n}{x}}dx}{logn}) \approx O(\frac{n^{\frac{3}{4}}}{logn})$$

代码：

#include <bits/stdc++.h>
#define ll long long
#define N 1000009
using namespace std;
ll n,pd[N],pri[N],cnt,g[2][N],m=1;
struct hash
{
    #define mod 19260817
    ll first[mod],number;
    struct edge
    {
        ll to,next,id,g,delta;
        void add(ll x,ll _id,ll _g,ll _delta,ll fir)
        {
            next=fir;
            id=_id,g=_g,delta=_delta;
        }
    }e[N];
    edge &operator [](const ll &_x)
    {
        int x=_x%mod;
        for (ll i=first[x];i;i=e[i].next)
            if (e[i].id==_x) return e[i];
        e[++number].add(x,_x,0,0,first[x]),first[x]=number;
        return e[number];
    }
    #undef mod
}mp;
void init()
{
    ll num=0;
    for (ll i=1;i<=n;i=(n/(n/i))+1)
        num++,mp[n/i].g=n/i,mp[n/i].delta=0;
    for (ll i=1;i<=m;i++)
        for (ll j=1;pri[i]*pri[i]<=n/j;j=(n/(n/j))+1)
        {
            ll now=n/j/pri[i];
            mp[n/j].g-=mp[now].g-(i-1-mp[now].delta);
            mp[n/j].delta=i;
        }
}
ll get(ll x)
{
    return mp[x].g-(m-mp[x].delta);
}
ll work()
{
    while (pri[m]*pri[m]<=n) m++;
    m--;
    ll ret=1;
    while (pri[ret]*pri[ret]*pri[ret]<=n) ret++;
    ret--;
    init();
    for (int i=1;pri[i]*pri[i]<=n;i++)
        ret+=get(n/pri[i])-get(pri[i]);
    return ret;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    pd[1]=1;
    for (int i=2;i<N;i++)
    {
        if (!pd[i]) pri[++cnt]=i;
        for (int j=1;j<=cnt&&pri[j]*i<N;j++)
        {
            pd[pri[j]*i]=1;
            if (!(i%pri[j])) break;
        }
    }
    cin>>n;
    cout<<work()<<endl;
    return 0;
}