【题解】Cookies 分块打表 hdu6753 ——quhengyi11

传送门

我做梦也没想到这题原来这样做.wva

首先看到 $n$的范围是 $10^{10}$，直觉告诉我复杂度肯定与 $\sqrt n$有关。

知道整个 $p_i$序列和最后的位置 $k$，很容易能倒退回删除之前的位置 $x$，这里就不讲了。

比较显然的一点是 $divmed(x) \leq \sqrt x$，更进一步讲：

$$divmed(x)=d(c \leq \sqrt x ,c | x,d\; is \; the\;maximum\; among\; c)$$

看起来并没有什么数学方法可以快速求 $divmed(x)$，我们考虑暴力求出所有 $divmed(x)$

我们可以从小到大枚举 $d$，记 $g(x) = divmed(x)$每次将 $1$到 $n$内所有 $d^2$的倍数都覆盖为 $g(x)=d$，类似埃筛，最后复杂度差不多是 $O(n)$的 (是一个级数，不会算，就取第一项吧)。

显然会爆，所以我们考虑打表？(oi 选手表示谁会想打表啊，代码长度限制 32KB，不过好像 ACM 赛场上没有代码长度限制 QAQ)

每 $up=10^5$为一段，记

$$a[i]=\sum_{j=(i-1)\times up+1}^{i \times up}g(j)$$

ll sieve (int x, int y)//\sum g(j)  j \in (x,y]
{
    int up = sqrt((double)y + 0.5);
    fo (i, 1, up)
    {
        ll d = 1ll * i * i;
        ll j = x / d * d + d;
        for (ll k = j, c = 1; k <= y; k += d, ++c)
            b[k - x] = i;
    }
    ll ret = 0;
    fo (i, 1, N) ret += b[i];
    return ret;
}

预处理出 $a[1..10^5]$，每次只需要再筛查一下剩下的部分就行了。

$gedit$打不开 $1M$的表，用 $vim$打开表然后在 $vimrc$里加上

set clipboard=unnamedplus

这样 $vim$里的剪贴板就与系统剪贴板相同了，可以通过 $vim$把代码剪贴出来。

后来发现，hdu 有代码长度限制。。。

掀桌！