莫比乌斯反演p1829

前言

此题用到了两次数论分块，学到许多，认识到分块的本质 本质是取整函数的函数值变化的停滞

一、题目

二、思路及代码 1.思路

题目是 ∑ i = 1 m ∑ j = 1 n l c m ( i , j ) \sum_{i=1}^{m}\sum_{j=1}^{n}lcm(i, j) i=1∑m​j=1∑n​lcm(i,j)我们一起来推下式子： = ∑ i = 1 m ∑ j = 1 n i j g c d ( i , j ) =\sum_{i=1}^{m}\sum_{j=1}^{n}\frac{ij}{gcd(i,j)} =i=1∑m​j=1∑n​gcd(i,j)ij​ = ∑ i = 1 m ∑ j = 1 n ∑ d = 1 i j [ d = g c d ( i , j ) ] d =\sum_{i=1}^{m}\sum_{j=1}^{n} \sum_{d=1}^{}\frac{ij[d=gcd(i,j)]}{d} =i=1∑m​j=1∑n​d=1∑​dij[d=gcd(i,j)]​ = ∑ d = 1 ∑ i = 1 ⌊ m d ⌋ ∑ j = 1 ⌊ n d ⌋ i j d [ 1 = g c d ( i , j ) ] =\sum_{d=1}^{}\sum_{i=1}^{\lfloor \frac{m}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor} {ijd[1=gcd(i,j)]} =d=1∑​i=1∑⌊dm​⌋​j=1∑⌊dn​⌋​ijd[1=gcd(i,j)] = ∑ d = 1 ∑ i = 1 ⌊ m d ⌋ ∑ j = 1 ⌊ n d ⌋ i j d ∑ t ∣ g c d ( i , j ) μ ( t ) =\sum_{d=1}^{}\sum_{i=1}^{\lfloor \frac{m}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor} ijd\sum_{t|gcd(i,j)}\mu(t) =d=1∑​i=1∑⌊dm​⌋​j=1∑⌊dn​⌋​ijdt∣gcd(i,j)∑​μ(t) = ∑ d = 1 d ∑ t = 1 μ ( t ) t 2 ∑ i = 1 ⌊ m d t ⌋ ∑ j = 1 ⌊ n d t ⌋ i j = \sum_{d=1}d\sum_{t=1}\mu(t)t^2\sum_{i=1}^{\lfloor \frac{m}{dt}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{dt}\rfloor}ij =d=1∑​dt=1∑​μ(t)t2i=1∑⌊dtm​⌋​j=1∑⌊dtn​⌋​ij 这时，我们的化简已经差不多了，我们便可以用数论分块来切题了 令 s u m ( ⌊ m d ⌋ , ⌊ n d ⌋ ) = ∑ t = 1 μ ( t ) t 2 ∑ i = 1 ⌊ m d t ⌋ ∑ j = 1 ⌊ n d t ⌋ i j 令 sum(\lfloor \frac{m}{d}\rfloor,\lfloor \frac{n}{d}\rfloor)=\sum_{t=1}\mu(t)t^2\sum_{i=1}^{\lfloor \frac{m}{dt}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{dt}\rfloor}ij 令sum(⌊dm​⌋,⌊dn​⌋)=t=1∑​μ(t)t2i=1∑⌊dtm​⌋​j=1∑⌊dtn​⌋​ij可初步获得此函数的结果，然后求 ∑ d = 1 d ∗ s u m ( ⌊ m d ⌋ , ⌊ n d ⌋ ) \sum_{d=1}d*sum(\lfloor \frac{m}{d}\rfloor,\lfloor \frac{n}{d}\rfloor) d=1∑​d∗sum(⌊dm​⌋,⌊dn​⌋)进而我们可在 O ( n ∗ n ) O(\sqrt{n}*\sqrt{n}) O(n ​∗n ​)时间内求出

2.代码

代码如下（示例）：

#include 
#define int long long
using namespace std;
const int maxn = 1e7 + 7;
const int mod = 20101009;
int miu[maxn], premiu[maxn];
int prime[maxn], pn;
bool isp[maxn];
void miu_table() {
  for (int i = 1; i