例题引路

题意

UVA11526 H(n) 求

\sum_{i = 1}^n\left\lfloor \frac n i\right\rfloor

n\lt 2^{31}

注意到 n 的范围很大,所以 O(n) 的算法是过不去的,考虑进行优化。我们首先假设 n = 10,然后可以发现答案的构成如下:

i:      1   2   3   4   5   6   7   8   9   10
n/i:    10  5   3   2   2   1   1   1   1   1

可以发现对于一段区间,这段区间里面的元素对答案的贡献是相同的,所以可以将整段分块,考虑每个块对答案的贡献。

不加证明地,结论就是每一段 i\in[x,\lfloor\frac{n}{\lfloor n/i\rfloor}\rfloor]\lfloor \frac n i\rfloor 的值都等于 \frac n x

整个算法的复杂度为 O(\sqrt n),证明等下说。

复杂度证明

求证:对于 x \in\mathbb{N^*}\lfloor \frac x i \rfloor,i\in[1,x] 的数量级是 O(\sqrt n) 级别的。

证明:对于 i\le \sqrt n\lfloor\frac n i\rfloor 至多有 \sqrt n 个取值,然后对于 i\gt \sqrt n\lfloor \frac n i\rfloor\lt \sqrt n,所以 \lfloor \frac n i\rfloor 也至多有 \sqrt n 种取值。所以 \lfloor\frac n i\rfloor 至多有 2\sqrt n 种取值。

上面的算法中,由于每种取值只计算了一遍,所以复杂度 O(\sqrt n)

分块右端点的证明

参考了李煜东《算法竞赛进阶指南》的证明。

g(i) = \displaystyle\lfloor\frac{n}{\lfloor\frac n i\rfloor}\rfloor。显然 f(i) = \displaystyle\frac n i 单调减,而 \displaystyle g(i)\ge \left\lfloor\frac{n}{\frac n i}\right\rfloor = x,所以 \displaystyle \frac{n}{g(i)}\le \lfloor\frac n i\rfloor。另外,\displaystyle \left\lfloor \frac{n}{g(i)}\right\rfloor\ge \left\lfloor\frac{n}{\frac{n}{\lfloor\frac n i\rfloor}}\right\rfloor = \lfloor\frac n i\rfloor,所以 \displaystyle\left\lfloor \frac{n}{g(i)}\right\rfloor = \lfloor\frac n i\rfloor。进一步可得,\forall x\in[i,g(i)]\displaystyle\left\lfloor\frac n i\right\rfloor 的值都相等。

所以第一次确定下 l =1,然后求出 r = g(l),统计这个块内的答案,再 l = r + 1,继续处理,得到最终答案。

例题代码实现

#include <cstdio>

typedef long long ll;

ll calc(ll n)
{
    ll ans = 0;
    for (ll l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        ans += (r - l + 1) * (n / l);
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        ll n;
        scanf("%lld", &n);
        printf("%lld\n", calc(n));
    }
    return 0;
}

另一道题

题意

P2261 [CQOI2007]余数求和

\displaystyle\sum_{i = 1}^n k\bmod i,其中 n,k\le 10^9

问题转化

由于 \displaystyle k\bmod i=k-i\times\left\lfloor\frac k i\right\rfloor,而 \left\lfloor\frac k i\right\rfloor 这个东西很明显可以数论分块做,于是考虑数论分块。

原式可以化为 nk -\displaystyle\sum_{i = 1}^n i\times\left\lfloor\frac k i\right\rfloor,注意到每一个块里面都是以 \displaystyle\left\lfloor\frac k i\right\rfloor 为公差的等差数列,所以直接套公式就可以了。

注意所有变量都要开 long long,然后由于 i \gt k 的部分是不会产生贡献的,所以在计算完 nk 之后直接把 n 赋值为 \min(n,k)。小心 g(l)\gt n 的情况,要取最小值

#include <cstdio>

typedef long long ll;

inline ll min(ll a, ll b){return a < b ? a : b;}

int main()
{
    ll n, k;
    scanf("%lld %lld", &n, &k);
    ll ans = n * k;
    n = min(n, k);
    for (ll l = 1, r; l <= n; l = r + 1)
    {
        r = min(k / (k / l), n);
        ans -= (r - l + 1) * (k / l * l) + ((r - l + 1) * (r - l) * (k / l)) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

模型的转化

题意

P3935 Calculating

x 分解质因数结果为 \prod p_i^{k_i},令 f(x) = \prod(k_i + 1),求 \displaystyle\sum_{i = l}^rf(i)。数据范围 1.6\times 10^{14}

思路

注意到 f(x) 实际上就是 x 的约数个数,故 \displaystyle\sum_{i=1}^nf(i) 是很容易预处理出来的,就是 \displaystyle\sum_{i = 1}^n\left\lfloor \frac n i\right\rfloor

证明:考虑在 [1,n] 中以 i 为约数的个数有 \displaystyle\left\lfloor \frac n i\right\rfloor 个,证毕。

所以直接套第一道模板题就可以了。

二维整除分块

题意

P2260 [清华集训2012]模积和

\sum_{i = 1}^n\sum_{j=1}^m(n\bmod i)\times(m\bmod j)\bmod 19940417,i\neq j

求解

先化一化式子:

不难发现,由容斥可展开为

\sum_{i=1}^n(n\bmod i)\times\sum_{j=1}^m(m\bmod j)-\sum_{i=1}^{\min\lbrace n, m\rbrace}(n\bmod i)\times(m\bmod i)

然后就是把模运算打开,此处为了简化记 \displaystyle f(n, k) = \sum_{i = 1}^n k\bmod i,原式可展开为

f(n,n)\times f(m,m)- \sum_{i=1}^{\min\lbrace n, m\rbrace}(nm – mi\left\lfloor \frac n i\right\rfloor-ni\left\lfloor\frac m i\right\rfloor + i^2\left\lfloor\frac n i\right\rfloor\left\lfloor\frac m i\right\rfloor)

稍加处理,得

f(n,n)\times f(m,m) – nm\min\lbrace n, m\rbrace+ nf(\min\lbrace n, m\rbrace, m) + mf(\min\lbrace n, m\rbrace, n) + \sum_{i=1}^{\min\lbrace n, m\rbrace}i^2\left\lfloor\frac n i\right\rfloor\left\lfloor\frac m i\right\rfloor

发现 f(n,k) 非常好求,最困扰人的是那一坨 \displaystyle \sum_{i=1}^{\min\lbrace n, m\rbrace}i^2\left\lfloor\frac n i\right\rfloor\left\lfloor\frac m i\right\rfloor 该如何处理。先考虑 \displaystyle \sum_{i=1}^{\min\lbrace n, m\rbrace}\left\lfloor\frac n i\right\rfloor\left\lfloor\frac m i\right\rfloor 的求法,发现其实也可以用整除分块来搞,只需要把每次块的右端点卡到 \displaystyle\left\lfloor\frac n i\right\rfloor=\left\lfloor\frac m i\right\rfloor 即可。对于 \sum i^2,可以套公式 \displaystyle\sum_{i=1}^n=\frac{n(n+1)(2n+1)}{6} 进行处理。

这题的坑点在于取模,该取模的时候一定要取模,然后三个数相乘是可能爆 long long 的,所以考虑直接处理出 2^{-1}\pmod {19940417}6^{-1}\pmod {19940417}

#include <cstdio>
#define il inline

typedef long long ll;

inline ll min(ll a, ll b){return a < b ? a : b;}

const ll mod = 19940417, inv2 = 9970209, inv6 = 3323403;

ll n, m, ans;

ll calc(ll n, ll k)
{
    ll ret = 0;
    n = min(n, k);
    for (ll l = 1, r = 1; l <= n; l = r + 1)
    {
        r = min(n, k / (k / l));
        ret += ((r - l + 1) * (k / l * l) % mod + (r - l + 1) * (r - l) % mod * (k / l) % mod * inv2 % mod) % mod;
        ret %= mod;
    }
    return ret;
}

il ll summod(ll n)
{
    return (n * n % mod - calc(n, n) + mod) % mod;
}

il ll sum(ll n)
{
    return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
}

ll calc2(ll n, ll m)
{
    ll top = min(n, m);
    ll ret = n * m % mod * top % mod;
    ret -= m * calc(top, n);
    ret = (ret + mod) % mod;
    ret -= n * calc(top, m);
    ret = (ret + mod) % mod;
    for (ll l = 1, r; l <= top; l = r + 1)
    {
        r = min(min(top, n / (n / l)), m / (m / l));
        ll sqri = sum(r) - sum(l - 1);
        ret = (ret + sqri * (n / l) % mod * (m / l) % mod) % mod;
    }
    return ret;
}

int main()
{
    scanf("%lld %lld", &n, &m);
    ans = summod(n) * summod(m) % mod;
    ans = (ans - calc2(n, m) + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}
最后修改日期:2020年12月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。