Description

定义F(n)表示最小公倍数为n的二元组的数量。 即：如果存在两个数（二元组）X，Y(X <= Y)，它们的最小公倍数为N，则F(n)的计数加1。 例如：F(6) = 5，因为[2,3] [1,6] [2,6] [3,6] [6,6]的最小公倍数等于6。

给出一个区间[a,b]，求最小公倍数在这个区间的不同二元组的数量。 例如：a = 4，b = 6。符合条件的二元组包括： [1,4] [2,4] [4,4] [1,5] [5,5] [2,3] [1,6] [2,6] [3,6] [6,6]，共10组不同的组合。

Solution

看到gcd就上反演系列~ 先把1~b的求出再减掉1~(a-1)。 Ans=∑i=1n√∑j=in⌊ni∗j⌋[gcd(i,j)=1] $$Ans=/sum_{i=1}^{/sqrt{n}}/sum_{j=i}^n/lfloor/frac{n}{i*j}/rfloor [gcd(i,j)=1]$$ 设gd$g_d$表示gcd为d的倍数的（辣一坨）的值得和， gd=∑i=1⌊nd2⌋∑j=i⌊nd2⌋⌊nij∗d2⌋ $$g_d=/sum_{i=1}^{/lfloor/frac{n}{d^2}/rfloor}/sum_{j=i}^{/lfloor/frac{n}{d^2}/rfloor}/lfloor/frac{n}{ij*d^2}/rfloor$$ 反演， Ans=∑d=1n√μ(i)∑i=1⌊nd2⌋∑j=i⌊nd2i⌋⌊nijd2⌋ $$Ans=/sum_{d=1}^{/sqrt{n}}/mu(i)/sum_{i=1}^{/lfloor/frac{n}{d^2}/rfloor}/sum_{j=i}^{/lfloor/frac{n}{d^2i}/rfloor}/lfloor/frac{n}{ijd^2}/rfloor$$ 设，（注意j的取值） T=∑i=1⌊nd2⌋∑j=1⌊nd2⌋⌊nijd2⌋ $$T=/sum_{i=1}^{/lfloor/frac{n}{d^2}/rfloor}/sum_{j=1}^{/lfloor/frac{n}{d^2}/rfloor}/lfloor/frac{n}{ijd^2}/rfloor$$ 则 Ans=12(n+∑d=1n√μ(i)T) $$Ans=/frac{1}{2}(n+/sum_{d=1}^{/sqrt{n}}/mu(i)T)$$ 这样还过不了，

看一下T，发现： T=∑i=1⌊nd2⌋∑j=1⌊nd2⌋∑k=1⌊nd2⌋[ijk<=⌊nd2⌋] $$T=/sum_{i=1}^{/lfloor/frac{n}{d^2}/rfloor}/sum_{j=1}^{/lfloor/frac{n}{d^2}/rfloor}/sum_{k=1}^{/lfloor/frac{n}{d^2}/rfloor}[ijk<=/lfloor/frac{n}{d^2}/rfloor]$$ 这个可以先保证i<=j<=k$i<=j<=k$，再算出两个相等的和三个相等的，容斥一波， 算的时候还可以用上分块

据说复杂度是:O(n23)$O(n^{/frac{2}{3}})$（不会算）

Code