传送门

我做梦也没想到这题原来这样做.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 有代码长度限制。。。

掀桌!

分类: 文章

quhengyi11

明日は何になる? やがて君になる!

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code