核心： r = n ÷ ( n ÷ l ) , l = r + 1 r=n\div (n\div l),l=r+1 r=n÷(n÷l),l=r+1
原理：被除数除以除数，商要尽可能大，而在 n ÷ l n\div l n÷l 一样的情况下就找最大的 r r r 。
拓展：多维数论分块，取最小值。如二维即为 r = m i n ( n ÷ ( n ÷ l ) , m ÷ ( m ÷ l ) ) r=min(n\div (n\div l),m\div (m\div l)) r=min(n÷(n÷l),m÷(m÷l)) 。
题意：求 ∑ i = l r f ( i ) \sum\limits_{i=l}^rf(i) i=l∑rf(i) ，其中 f ( i ) = ∑ k = 1 i [ k ∣ i ] f(i)=\sum\limits_{k=1}^i [k|i] f(i)=k=1∑i[k∣i] 。
思路：很妙。设 g ( x ) = ∑ i = 1 x f ( i ) = ∑ i = 1 x ∑ k = 1 i [ k ∣ i ] g(x)=\sum\limits_{i=1}^x f(i)=\sum\limits_{i=1}^x \sum\limits_{k=1}^i [k|i] g(x)=i=1∑xf(i)=i=1∑xk=1∑i[k∣i] 。
**关键在交换主体，**试着把 k k k 提到外面来减小计算量。
k k k 能够取 [ 1 , x ] [1,x] [1,x] ，那么 i i i 能取它的倍数，于是 g ( x ) = ∑ k = 1 x ∑ i = 1 x [ k ∣ i ] g(x)=\sum\limits_{k=1}^{x}\sum\limits_{i=1}^x[k|i] g(x)=k=1∑xi=1∑x[k∣i] 。
观察到后面那个式子可以减小计算量，于是 g ( x ) = ∑ k = 1 x ⌊ x k ⌋ g(x)=\sum\limits_{k=1}^x ⌊\dfrac{x}{k}⌋ g(x)=k=1∑x⌊kx⌋ 。
于是就是整除分块的事了。
题意：求 ∑ i = 1 n ∑ j = 1 n gcd ( i , j ) \sum\limits_{i=1}^n\sum\limits_{j=1}^n \gcd(i,j) i=1∑nj=1∑ngcd(i,j) 。
转化：很容易想到合并同类项，提取出来 gcd ( i , j ) \gcd(i,j) gcd(i,j) 。
于是，原式= ∑ g = 1 n g ∑ i = 1 ⌊ n g ⌋ ∑ j = 1 ⌊ n g ⌋ [ gcd ( i , j ) = 1 ] \sum\limits_{g=1}^n g\sum\limits_{i=1}^{⌊\tfrac{n}{g}⌋}\sum\limits_{j=1}^{⌊\tfrac{n}{g}⌋}[\gcd(i,j)=1] g=1∑ngi=1∑⌊gn⌋j=1∑⌊gn⌋[gcd(i,j)=1]
我们知道欧拉函数 φ ( i ) = ∑ j = 1 i − 1 [ gcd ( i , j ) = 1 ] \varphi(i)=\sum_{j=1}^{i-1} [\gcd(i,j)=1] φ(i)=∑j=1i−1[gcd(i,j)=1] ，所以 ∑ i = 1 m ∑ j = 1 m [ gcd ( i , j ) = 1 ] = 2 ∑ i = 1 m φ ( i ) − 1 \sum\limits_{i=1}^m\sum\limits_{j=1}^m [\gcd(i,j)=1]=2\sum\limits_{i=1}^m \varphi(i)-1 i=1∑mj=1∑m[gcd(i,j)=1]=2i=1∑mφ(i)−1
于是原式= ∑ g = 1 n g ∑ i = 1 ⌊ n g ⌋ φ ( i ) \sum\limits_{g=1}^n g\sum\limits_{i=1}^{⌊\tfrac{n}{g}⌋}\varphi(i) g=1∑ngi=1∑⌊gn⌋φ(i) 。
前面可以预处理得欧拉函数的前缀和，所以答案就可以
O
(
n
)
O(n)
O(n) 求出。这和整除分块有什么关系？
求 ∑ i = 1 n ∑ j = 1 m gcd ( i , j ) \sum\limits_{i=1}^n\sum\limits_{j=1}^{m} \gcd(i,j) i=1∑nj=1∑mgcd(i,j) 。
另外一种做法是莫比乌斯反演。
考虑这样一个东西： ∑ d ∣ n μ ( d ) = [ n = 1 ] = ϵ ( n ) \sum\limits_{d|n}\mu(d)=[n=1]=ϵ(n) d∣n∑μ(d)=[n=1]=ϵ(n) （莫比乌斯函数的性质）
原式= ∑ g = 1 min ( n , m ) g ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = g ] \sum\limits_{g=1}^{\min(n,m)}g\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=g] g=1∑min(n,m)gi=1∑nj=1∑m[gcd(i,j)=g]
= ∑ g = 1 min ( n , m ) g ∑ i = 1 ⌊ n g ⌋ ∑ j = 1 ⌊ m g ⌋ [ gcd ( i , j ) = 1 ] \sum\limits_{g=1}^{\min(n,m)}g\sum\limits_{i=1}^{\left\lfloor\frac{n}{g}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{g}\right\rfloor} [\gcd(i,j)=1] g=1∑min(n,m)gi=1∑⌊gn⌋j=1∑⌊gm⌋[gcd(i,j)=1]
这个时候做莫比乌斯反演，
= ∑ g = 1 min ( n , m ) g ∑ i = 1 ⌊ n g ⌋ ∑ j = 1 ⌊ m g ⌋ ∑ d ∣ gcd ( i , j ) μ ( d ) \sum\limits_{g=1}^{\min(n,m)}g\sum\limits_{i=1}^{\left\lfloor\frac{n}{g}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{g}\right\rfloor}\sum\limits_{d|\gcd(i,j)} \mu(d) g=1∑min(n,m)gi=1∑⌊gn⌋j=1∑⌊gm⌋d∣gcd(i,j)∑μ(d)
发现并不好处理，所以把 d d d 提取到前面，即先枚举 d d d ，这样就能消掉 d ∣ gcd ( i , j ) d|\gcd(i,j) d∣gcd(i,j) 这一条件了。
所以符合条件的 i , j i,j i,j 都是 d d d 的倍数，即：
= ∑ g = 1 min ( n , m ) g ∑ d = 1 ⌊ min ( n , m ) d ⌋ μ ( d ) ∑ i = 1 ⌊ n g d ⌋ ∑ j = 1 ⌊ m g d ⌋ 1 \sum\limits_{g=1}^{\min(n,m)}g\sum\limits_{d=1}^{\left\lfloor\frac{\min(n,m)}{d}\right\rfloor} \mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{gd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{gd}\right\rfloor}1 g=1∑min(n,m)gd=1∑⌊dmin(n,m)⌋μ(d)i=1∑⌊gdn⌋j=1∑⌊gdm⌋1
= ∑ g = 1 min ( n , m ) g ∑ d = 1 ⌊ min ( n , m ) d ⌋ μ ( d ) ⌊ n g d ⌋ ⌊ m g d ⌋ \sum\limits_{g=1}^{\min(n,m)}g\sum\limits_{d=1}^{\left\lfloor\frac{\min(n,m)}{d}\right\rfloor} \mu(d){\left\lfloor\frac{n}{gd}\right\rfloor}{\left\lfloor\frac{m}{gd}\right\rfloor} g=1∑min(n,m)gd=1∑⌊dmin(n,m)⌋μ(d)⌊gdn⌋⌊gdm⌋
两个 g g g 和 d d d 不好处理，枚举 g d gd gd ，设 g d = T gd=T gd=T ，那么原式= ∑ T = 1 min ( n , m ) ⌊ n T ⌋ ⌊ m T ⌋ ∑ d ∣ T μ ( d ) \sum\limits_{T=1}^{\min(n,m)} {\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}\sum\limits_{d|T} \mu(d) T=1∑min(n,m)⌊Tn⌋⌊Tm⌋d∣T∑μ(d) 。
至此，我们就可以把左半部分用整除分块做，右半部分用对于每个 T T T 线性筛筛出来。
时间复杂度 O ( n + T n ) O(n+T\sqrt {n} ) O(n+Tn)。