分析
显然我们需要往莫比乌斯函数的方向考虑。因此,我们要把 lcm(i,j) 换作使用 gcd(i,j) 表示。
为了方便,下文中假设 n≤m(如果 n>m 那么两者交换一下就好了)。
i=1∑nj=1∑mlcm(i,j)=i=1∑nj=1∑mgcd(i,j)ij
我们发现 gcd(i,j) 位于分母,这十分不好处理。因此我们在这里介绍一个技巧,令 gcd(i,j)=k 并枚举 k 从而使得 gcd(i,j) 离开分母:
i=1∑nj=1∑mlcm(i,j)==i=1∑nj=1∑mk=1∑nkij[gcd(i.j)=k]k=1∑min(n,m)i=1∑⌊kn⌋j=1∑⌊km⌋ijk[gcd(i,j)=1]
终于出现了我们最喜闻乐见的 [gcd(i,j)=1],我们按套路对其进行变换:
i=1∑nj=1∑mlcm(i,j)=====k=1∑ni=1∑⌊kn⌋j=1∑⌊km⌋ijkd∣gcd(i,j)∑μ(d)k=1∑ni=1∑⌊kn⌋j=1∑⌊km⌋ijkd=1∑⌊kn⌋μ(d)[d∣gcd(i,j)]k=1∑nkd=1∑⌊kn⌋μ(d)i=1∑⌊kn⌋j=1∑⌊km⌋ij[d∣gcd(i,j)]k=1∑nkd=1∑⌊kn⌋μ(d)i=1∑⌊kdn⌋j=1∑⌊kdm⌋ijd2[1∣gcd(i,j)]k=1∑nkd=1∑⌊kn⌋μ(d)d2i=1∑⌊kdn⌋ij=1∑⌊kdm⌋j
我们注意到最后两项实际上都是等差数列求和。我们不妨令 g(i)=i=1∑ni,那么有:
i=1∑nj=1∑mlcm(i,j)=k=1∑nkd=1∑⌊kn⌋μ(d)d2g(⌊kdn⌋)g(⌊kdm⌋)
令 T=kd,同时我们考虑枚举 T,则有:
i=1∑nj=1∑mlcm(i,j)===k=1∑nkd=1∑⌊kn⌋μ(d)d2g(⌊Tn⌋)g(⌊Tm⌋)T=1∑ng(⌊Tn⌋)g(⌊Tm⌋)d∣T∑μ(d)d2dTT=1∑ng(⌊Tn⌋)g(⌊Tm⌋)Td∣T∑dμ(d)
不妨令 F(n)=d∣n∑dμ(d) 并对 F(n) 进行研究。
我们发现,当 a⊥b 时(当 a,b 互质时):
F(a)=F(b)=d∣a∑dμ(d)d∣b∑dμ(d)
我们不难发现,由 a⊥b,故 a 和 b 不存在公共因子,因此 i∣a, j∣b⇔ij∣ab。又由于 μ(n) 本身又是积性函数,所以有 μ(ab)=μ(a)⋅μ(b)。由此:
F(a)⋅F(b)====i∣a∑iμ(i)j∣b∑jμ(j)ij∣ab∑ij⋅μ(ij)k∣ab∑kμ(k)F(ab)
我们发现 F(n) 也是个积性函数!既然是积性函数…… 那么一定可以线性筛:
- F(1)=1;
- 若 a 是质数,F(a)=1−a;
- 若 a⊥b,F(ab)=F(a)⋅F(b);
由此一来,我们就可以 O(N) 初始化(线性筛 F(n)),并借助整除分块 O(N) 解决询问了。
最后附上 我的代码 以供参考。