数论分块

对于某些数列求和操作，求和的项数过大，直接求和会超时，但是数列中数的种数较少，且相同的数分布连续。此时需要找到一种方式能快速求出每种数的分布边界，然后枚举每一种数快速求和。

基本形式类似于
∑ i = 1 n f ( i ) g ( ⌊ n r ( i ) ⌋ ) \sum_{i=1}^nf(i)g(\left \lfloor\frac{n}{r(i)} \right \rfloor) i=1∑n​f(i)g(⌊r(i)n​⌋)

常用结论

• ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ \left \lfloor \frac{a}{bc} \right \rfloor=\left \lfloor\frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} \right \rfloor ⌊bca​⌋=⌊c⌊ba​⌋​⌋

  证明：

  设
  a b = ⌊ a b ⌋ + r   ( 0 ≤ r < 1 ) \frac{a}{b}=\left \lfloor \frac{a}{b} \right \rfloor+r\ (0\le r<1) ba​=⌊ba​⌋+r (0≤r<1)
  则
  ⌊ a b c ⌋ = ⌊ a b ⋅ 1 c ⌋ = ⌊ 1 c ⋅ ( ⌊ a b ⌋ + r ) ⌋ = ⌊ ⌊ a b ⌋ c + r c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ \left \lfloor \frac{a}{bc} \right \rfloor=\left \lfloor \frac{a}{b}\cdot\frac{1}{c} \right \rfloor=\left \lfloor\frac{1}{c}\cdot(\left \lfloor\frac{a}{b} \right \rfloor+r) \right \rfloor=\left \lfloor\frac{\left \lfloor\frac{a}{b} \right \rfloor}{c} +\frac{r}{c} \right \rfloor=\left \lfloor\frac{\left \lfloor \frac{a}{b} \right \rfloor}{c} \right \rfloor ⌊bca​⌋=⌊ba​⋅c1​⌋=⌊c1​⋅(⌊ba​⌋+r)⌋=⌊c⌊ba​⌋​+cr​⌋=⌊c⌊ba​⌋​⌋
  得证。

• ∀ n ∈ N + , ∣ { ⌊ n d ⌋ ∣ d ∈ N + , d ≤ n } ∣ ≤ ⌊ 2 n ⌋ \forall n\in\mathbb{N}_+,\left|\left\{ \left\lfloor \frac{n}{d} \right\rfloor \mid d \in \mathbb{N}_+,d\leq n \right\}\right| \leq \left \lfloor 2\sqrt{n} \right\rfloor ∀n∈N+​,∣∣∣​{⌊dn​⌋∣d∈N+​,d≤n}∣∣∣​≤⌊2n ​⌋

• max ⁡ ⌊ n r ⌋ = ⌊ n l ⌋ r = ⌊ n ⌊ n l ⌋ ⌋ \max_{\left \lfloor \frac{n}{r} \right \rfloor=\left \lfloor \frac{n}{l} \right \rfloor}r=\left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor ⌊rn​⌋=⌊ln​⌋max​r=⌊⌊ln​⌋n​⌋

  证明：

  因为
  ⌊ n r ⌋ = ⌊ n l ⌋ \left \lfloor \frac{n}{r} \right \rfloor=\left \lfloor \frac{n}{l} \right \rfloor ⌊rn​⌋=⌊ln​⌋
  所以
  n r ≥ ⌊ n l ⌋ \frac{n}{r}\geq\left \lfloor \frac{n}{l} \right \rfloor rn​≥⌊ln​⌋
  即
  r ≤ n ⌊ n l ⌋ r\le\frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} r≤⌊ln​⌋n​
  因此
  max ⁡ r = ⌊ n ⌊ n l ⌋ ⌋ \max r=\left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor}\right \rfloor maxr=⌊⌊ln​⌋n​⌋

• ∀ i ∈ ( 1 , n ] , ⌊ n i − 1 ⌋ ≠ ⌊ n i ⌋ , ⌊ n ⌊ n i − 1 ⌋ ⌋ ≠ ⌊ n ⌊ n i ⌋ ⌋ \forall i\in(1,\sqrt n],\left \lfloor \frac{n}{i-1} \right \rfloor\not =\left \lfloor\frac{n}{i} \right \rfloor,\left \lfloor \frac{n}{\left \lfloor \frac{n}{i-1} \right \rfloor} \right \rfloor\not =\left \lfloor \frac{n}{\left \lfloor\frac{n}{i} \right \rfloor} \right \rfloor ∀i∈(1,n ​],⌊i−1n​⌋​=⌊in​⌋,⌊⌊i−1n​⌋n​⌋​=⌊⌊in​⌋n​⌋

  证明：由于 n x \frac{n}{x} xn​ 作为反比例函数，导数的绝对值随 x x x 的增长而减小，因此只需证明 i = n i=\sqrt n i=n ​ 时成立即可。

  因为
  n n − 1 − n n = n + n n − 1 > 1 \frac{n}{\sqrt n-1}-\frac{n}{\sqrt n}=\frac{n+\sqrt n}{n-1}>1 n ​−1n​−n ​n​=n−1n+n ​​>1
  因此
  ⌊ n n − 1 ⌋ ≠ ⌊ n n ⌋ \left \lfloor\frac{n}{\sqrt n-1} \right \rfloor\not =\left \lfloor\frac{n}{\sqrt n} \right \rfloor ⌊n ​−1n​⌋​=⌊n ​n​⌋
  因此
  ∀ i ∈ ( 1 , n ] , ⌊ n i − 1 ⌋ ≠ ⌊ n i ⌋ \forall i\in(1,\sqrt n],\left \lfloor \frac{n}{i-1} \right \rfloor\not =\left \lfloor\frac{n}{i} \right \rfloor ∀i∈(1,n ​],⌊i−1n​⌋​=⌊in​⌋
  结合上一结论可知
  ⌊ n ⌊ n i − 1 ⌋ ⌋ ≠ ⌊ n ⌊ n i ⌋ ⌋ \left \lfloor \frac{n}{\left \lfloor \frac{n}{i-1} \right \rfloor} \right \rfloor\not =\left \lfloor \frac{n}{\left \lfloor\frac{n}{i} \right \rfloor} \right \rfloor ⌊⌊i−1n​⌋n​⌋​=⌊⌊in​⌋n​⌋
  同样成立。

常见形式

• ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^n\left \lfloor\frac{n}{i} \right \rfloor i=1∑n​⌊in​⌋

  枚举 l l l ，求 max ⁡ ⌊ n r ⌋ = ⌊ n l ⌋ r = ⌊ n ⌊ n l ⌋ ⌋ \max_{\left \lfloor \frac{n}{r} \right \rfloor=\left \lfloor \frac{n}{l} \right \rfloor}r=\left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor max⌊rn​⌋=⌊ln​⌋​r=⌊⌊ln​⌋n​⌋，然后在答案上累加 ( r − l + 1 ) ⌊ n l ⌋ (r-l+1)\left \lfloor \frac{n}{l} \right \rfloor (r−l+1)⌊ln​⌋，并更新 l = r + 1 l=r+1 l=r+1 。

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

• ∑ i = 1 min ⁡ ( n , m ) ⌊ n i ⌋ ⌊ m i ⌋ \sum_{i=1}^{\min(n,m)}\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{i} \right \rfloor i=1∑min(n,m)​⌊in​⌋⌊im​⌋

  每次取右边界 r = min ⁡ ( ⌊ n ⌊ n i ⌋ ⌋ , ⌊ m ⌊ m i ⌋ ⌋ ) r=\min(\left \lfloor \frac{n}{\left \lfloor\frac{n}{i} \right \rfloor} \right \rfloor,\left \lfloor \frac{m}{\left \lfloor\frac{m}{i} \right \rfloor} \right \rfloor) r=min(⌊⌊in​⌋n​⌋,⌊⌊im​⌋m​⌋) 即可。

      for (ll l = 1, r; l <= min(n, m); l = r + 1) {
          r = min(n / (n / i), m / (m / i));
          ans += (r - l + 1) * (n / l) * (m / l);
      }
  

• ∑ i = 1 n f ( i ) ⌊ n i ⌋ \sum_{i=1}^nf(i)\left \lfloor \frac{n}{i} \right \rfloor i=1∑n​f(i)⌊in​⌋

  如果 f ( i ) f(i) f(i) 存在求和公式，则每次往答案累加 ( f ( r ) − f ( l − 1 ) ) ⌊ n l ⌋ (f(r)-f(l-1))\left \lfloor \frac{n}{l} \right \rfloor (f(r)−f(l−1))⌊ln​⌋ 。

• ∑ k = 1 n ∑ k ∣ x n x \sum_{k=1}^n\sum_{k|x}^nx k=1∑n​k∣x∑n​x

  ∑ k ∣ x n x \sum_{k|x}^nx ∑k∣xn​x 部分可以看做是首项为 k k k ，公差为 k k k ，项数为 ⌊ n k ⌋ \left \lfloor \frac{n}{k} \right \rfloor ⌊kn​⌋ 的等差数列求和，故可写成
  ∑ k = 1 n k ( ⌊ n k ⌋ + 1 ) ⌊ n k ⌋ 2 \sum_{k=1}^n\frac{k(\left \lfloor\frac{n}{k} \right \rfloor+1)\left \lfloor\frac{n}{k} \right \rfloor}{2} k=1∑n​2k(⌊kn​⌋+1)⌊kn​⌋​
  观察发现，式子中的变量只有 ⌊ n k ⌋ \left \lfloor\frac{n}{k} \right \rfloor ⌊kn​⌋ 和 k k k ，因此可以通过整除分块求解。

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

• ∑ i = 1 n ⌊ n f ( i ) ⌋ \sum_{i=1}^n\left \lfloor \frac{n}{f(i)} \right \rfloor i=1∑n​⌊f(i)n​⌋

  仅需考虑 f ( i ) ≤ n f(i)\le n f(i)≤n 的部分。对于 l l l ，可求得

  r = ⌊ f − 1 ( ⌊ n ⌊ n f ( l ) ⌋ ⌋ ) ⌋ r=\left \lfloor f^{-1}(\left \lfloor \frac{n}{\left \lfloor \frac{n}{f(l)} \right \rfloor} \right \rfloor)\right \rfloor r=⎣⎢⎢⎢​f−1(⎣⎢⎢⎢​⌊f(l)n​⌋n​⎦⎥⎥⎥​)⎦⎥⎥⎥​
  然后在答案上累加 ( r − l + 1 ) ⌊ n f ( l ) ⌋ (r-l+1)\left \lfloor \frac{n}{f(l)} \right \rfloor (r−l+1)⌊f(l)n​⌋，并更新 l = r + 1 l=r+1 l=r+1 。

  例如 f ( x ) = x 2 f(x)=x^2 f(x)=x2 的情况下：

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

• ∑ i = 1 n ⌈ n i ⌉ \sum_{i=1}^n\left \lceil \frac{n}{i} \right \rceil i=1∑n​⌈in​⌉

  因为
  ⌈ n i ⌉ = { ⌊ n i ⌋ i ∣ n ⌊ n i ⌋ + 1 i ∤ n \left \lceil \frac{n}{i} \right \rceil=\left\{\begin{matrix} \left \lfloor \frac{n}{i} \right \rfloor&&i|n\\ \left \lfloor \frac{n}{i} \right \rfloor+1&&i\nmid n \end{matrix}\right. ⌈in​⌉={⌊in​⌋⌊in​⌋+1​​i∣ni∤n​
  假设 n n n 的约数个数为 d ( n ) d(n) d(n) ，则
  ∑ i = 1 n ⌈ n i ⌉ = n − d ( n ) + ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^n\left \lceil \frac{n}{i} \right \rceil=n-d(n)+\sum_{i=1}^n\left \lfloor\frac{n}{i} \right \rfloor i=1∑n​⌈in​⌉=n−d(n)+i=1∑n​⌊in​⌋