Contents
例题引路
题意
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;
}
留言