数论分块

· · 个人记录

可结合题单：数论专题II食用

UVA11526 H(n)

题目描述

分析

把它写成数学的式子就是求：

首先，通过大眼观察法或者打表可以发现，其中有很多值都是重复的。 比如 $n=5$ 时，$\left\lfloor\dfrac{n}{i}\right\rfloor$ 分别为 ${5,2,1,1,1}$。 考虑每次计算直接一起算出重复的值。 观察值为 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 的块的右边界，因为每次左边界都会有上一次右边界推出（也就是 $i$）所以不用管。 右边界也就是值为 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 的 $i$ 最大的那一个，考虑什么时候可以取得到。 其实右边界是 $\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor$。可以感性理解。 想要详细证明可以看 [这个](https://www.luogu.com.cn/blog/486187/awawawa#:~:text=两种证明方式)。 现在每个块内值相等，都为 $\left\lfloor\dfrac{n}{i}\right\rfloor$，每块一共有 $j-i+1$ 个数，每次加上就好。 这样可以证明时间复杂度是 $\mathcal{O}(\sqrt n)$ 的，下面会证。 ```cpp typedef long long ll; ll f(ll n){ ll ans=0; for(ll i=1,j;i<=n;i=j+1){ j=n/(n/i); ans=(ans+n/i%mod*(j-i+1))%mod; } return ans; } ``` ### 复杂度证明： - 当 $x \in [1, \lfloor\sqrt n\rfloor]$ 这个区间，最多有 $\lfloor\sqrt n\rfloor$ 种取值。 - 当 $x \in (\lfloor\sqrt n\rfloor,n]$ 这个区间，$\lfloor\dfrac n x\rfloor$ 显然只能取到 $[1,\lfloor\sqrt n\rfloor)$ 这个区间，最多有 $\lfloor\sqrt n\rfloor$ 种取值。 则至多有 $2\lfloor\sqrt n\rfloor$ 种取值，复杂度为 $\mathcal{O}(\sqrt n)$。 --- ### [P1403 [AHOI2005]约数研究](https://www.luogu.com.cn/problem/P1403) 即求 $1\sim n$ 约数个数的和。 注意到 $1\sim n$ 的因子个数，可以看成共含有 $2$ 因子的数的个数+含有 $3$ 因子的数的个数+......+含有 $n$ 因子的数的个数 但在 $1\sim n$ 中含有 $2$ 这个因子的数有 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 个，$3$ 有 $\left\lfloor\dfrac{n}{3}\right\rfloor$ 个，以此类推。 问题就转化为了刚刚我们做出来的式子：$\sum\limits_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor$。 用同样的数论分块去做。 ~~因为这题是橙题，所以直接暴力算式子也是可以的。~~ ### 相关习题 - [P2261 [CQOI2007]余数求和](https://www.luogu.com.cn/problem/P2261) 注意式子转化。 - [P2424 约数和](https://www.luogu.com.cn/problem/P2424) 注意区别，这里求的是约数和，那么每一块再套一个求和公式呗。 - [P3935 Calculating](https://www.luogu.com.cn/problem/P3935) 你得知道这是约数个数定理。 --- ### [P2260 [清华集训2012]模积和](https://www.luogu.com.cn/problem/P2260) 求 $\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j$ mod 19940417 的值 - 对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10^9$。 什么东西，先看那个 $i\not=j$ 不顺眼，先拆了。 $$\sum_{i=1}^{n}(n \bmod i) \times \sum_{j=1}^{m} (m \bmod j)-\sum_{i=1}^{n}(n \bmod i) \times (m \bmod i)$$ 看起来就不好搞，用 $a \bmod b=a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b$ 拆了。 $$\sum_{i=1}^{n} (n-\left\lfloor\dfrac{n}{i}\right\rfloor\times i) \times \sum_{j=1}^{m} (m-\left\lfloor\dfrac{m}{j}\right\rfloor\times j)-\sum_{i=1}^{n}(n-\left\lfloor\dfrac{n}{i}\right\rfloor\times i) \times (m-\left\lfloor\dfrac{m}{i}\right\rfloor\times i)$$ 看起来就可以用算了分块做，接着拆。 $$(n^2-\sum_{i=1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor\times i )\times (m^2-\sum_{j=1}^{m} \left\lfloor\dfrac{m}{j}\right\rfloor\times j)-\sum_{i=1}^{n}(n\times m-n\times (\left\lfloor\dfrac{m}{i}\right\rfloor\times i)-m\times(\left\lfloor\dfrac{n}{i}\right\rfloor\times i)+(\left\lfloor\dfrac{n}{i}\right\rfloor\times i\times \left\lfloor\dfrac{m}{i}\right\rfloor\times i))$$ 左边的已经可以用数论分块做了，现在看右边那一坨。 $$\sum_{i=1}^{n}(n\times m-n\times (\left\lfloor\dfrac{m}{i}\right\rfloor\times i)-m\times(\left\lfloor\dfrac{n}{i}\right\rfloor\times i)+(\left\lfloor\dfrac{n}{i}\right\rfloor\times i\times \left\lfloor\dfrac{m}{i}\right\rfloor\times i))$$ $$n\times n\times m-n\sum_{i=1}^{n}(\left\lfloor\dfrac{m}{i}\right\rfloor\times i)-m\times \sum_{i=1}^{n}(\left\lfloor\dfrac{n}{i}\right\rfloor\times i)+\sum_{i=1}^{n}(i^2\times \left\lfloor\dfrac{n}{i}\right\rfloor\times \left\lfloor\dfrac{m}{i}\right\rfloor)$$ 前面三项可以用数论分块做，最后一项怎么办？ 其实还是数论分块，只不过把 `j=n/(n/i)` 换成了 `j=min(n/(n/i),m/(m/i))`，想一想为什么。然后发现，知道了左右边界也不会计算 $\sum\limits_{i=1}^{n}i^2$，~~诶这不是小学 XES 讲过的踢三角证明吗~~，然后我们就应该知道：$\sum\limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6}$。 然后调亿会儿就好了。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=19940417; const int inv2=9970209; const int inv6=3323403; ll n,m; inline ll sum1(ll l,ll r){ return (l+r)*(r-l+1)%mod*inv2%mod; } inline ll sum2(ll l,ll r){ return (r*(r+1)%mod*(r+r+1)%mod-(l-1)*l%mod*(l+l-1)%mod)*inv6%mod; } ll fn(ll n){ ll ans=0; for(ll i=1,j;i<=n;i=j+1){ j=n/(n/i); ans=(ans+(n/i)*sum1(i,j)%mod)%mod; } return ans; } ll fm(ll m){ ll ans=0; for(ll i=1,j;i<=n;i=j+1){ j=min(m/(m/i),n); ans=(ans+(m/i)*sum1(i,j)%mod)%mod; if(i==n) break; } return ans; } ll fnm(ll n,ll m){ ll ans=0; for(ll i=1,j;i<=n;i=j+1){ j=min(n/(n/i),m/(m/i)); ans=(ans+(n/i)*(m/i)%mod*sum2(i,j)%mod)%mod; } return ans; } int main() { scanf("%lld%lld",&n,&m); if(n>m) swap(n,m); ll tmp1=(n*n%mod-fn(n))%mod,tmp2=(m*m-fn(m))%mod; ll tmp3=(n*n%mod*m%mod-m*fn(n)%mod-n*fm(m)%mod+fnm(n,m)%mod)%mod; printf("%lld\n",((tmp1*tmp2%mod-tmp3)%mod+mod)%mod); return 0; } ``` ### 公式 话说这些公式还是比较有用的吧。 $\sum\limits_{i=1}^{n}i=\dfrac{n(n+1)}{2} \sum\limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6} \sum\limits_{i=1}^{n}i^3=(\sum\limits_{i=1}^{n}i)^2=\dfrac{n^2(n+1)^2}{4}

推荐阅读

浅谈数论分块