题目大意
求满足如下条件的数对$(a,b)$对数:$a,b$均为正整数且$a,b\le n$而$lcm(a,b)\gt n$。其中的$lcm$当然表示最小公倍数。答案对1,000,000,007取模。
题目分析
显然$lcm(a,b)\gt n$不那么好直接求解，我们运用补集转化的思想，转为$lcm(a,b)\le n$的方案数。
确定答案多项式
统计$lcm(a,b)\le n$的方案数，当$a,b$给定时，$ab=gcd(a,b)lcm(a,b)$。
将$a,b$中的$gcd$除掉，变为：$a’b’gcd(a,b)=lcm(a,b)$，记$gcd(a,b)$为$d$，因此我们应该统计$a’b’d\le n$的个数，其中$a’,b’$互质。
为了方便，在下文中重新将$a’,b’$记作$a,b$，将$gcd(a,b)$记作$(a,b)$。
当$a,b$确定时，$d$的取值有$\lfloor \frac{n}{ab} \rfloor$种。
故：
莫比乌斯反演
很显然，上述式子可以莫比乌斯反演。
我们用$\sum_{k|a,k|b}\mu(k)$来替换$[(a,b)=1]$，这是莫比乌斯反演中一个重要的恒等式。
那么我们就可以得到：
接着我们将$\sum_k$提取到整个式子的最外部：
将$a,b$枚举范围改一下形式：
莫比乌斯反演到这一步就无法继续化简了，但是我们仍不能得到一个快速的算法来计算它的值。
考虑什么情况是必定没有贡献的：
式子最右端的$\lfloor \frac{n}{abk^2} \rfloor$说明当$k^2>n$的时候是必定没有贡献的，因此$k$的上界可以缩减为$\sqrt{n}$。
我们得到了一个更高效的式子：
实际上我们还可以继续优化：
发现当$a$枚举到$\lfloor \frac{n}{k}\rfloor$，$b$枚举到$1$时，$\lfloor \frac{n}{abk^2} \rfloor$的值约为$\frac{1}{k}$，对答案是肯定没有贡献的，因此我们可以进一步缩减$a,b$的枚举范围。
根据式子$\lfloor \frac{n}{abk^2} \rfloor$，显然$ab$最大为$\lfloor \frac{n}{k^2}\rfloor$的时候仍有贡献，再大肯定没有贡献了。
因此我们可以得出最终的式子：
换元
式子有点复杂，我们换个元看看。
我们发现这段式子$\sum_{a=1}^{\lfloor \frac{n}{k^2}\rfloor}\sum_{b=1}^{\lfloor \frac{n}{k^2}\rfloor}\lfloor \frac{n}{abk^2} \rfloor$仅与$\frac{n}{k^2}$有关，
则记$f(\frac{n}{k^2})$为$\sum_{a=1}^{\lfloor \frac{n}{k^2}\rfloor}\sum_{b=1}^{\lfloor \frac{n}{k^2}\rfloor}\lfloor \frac{n}{abk^2} \rfloor$。
原式变为：
求解函数f(x)
观察$f$函数：
我们发现这是一个用根号跳跃法解决的经典式子，根据$\lfloor \frac{x}{i}\rfloor$的取值分块，那么每一块的答案即为$\sum_{j=1}^{\lfloor \frac{x}{i}\rfloor}\lfloor \frac{\frac{x}{i}}{j} \rfloor$，后面部分仅与$\lfloor \frac{x}{i}\rfloor$有关，我们将其记为$g(\lfloor \frac{x}{i}\rfloor)$。
求解函数g(x)
显然这个式子等价于：
$d(i)$表示$i$的约数个数。
为什么呢？因为$\lfloor \frac{x}{i}\rfloor$表示$x$以内有多少个数能被$i$整除，那么它肯定能够完全地被$d(i)$统计完。
这说明什么，$g$函数可以使用线性筛来解决，不会的可以看一下这里。
但是$n$的范围有这么大：$10000000000$，线性筛都会超时。
怎么办呢？我们可以计算$n^{\frac{2}{3}}$内的$d$函数，大概认为在$4000000$内的$d$函数。
那剩下的怎么办呢？暴力计算啊。
我们发现：
$g$函数的式子依然可以分块，因此我们就可以快速求出$g$函数了。
优化
似乎在某些平台这样做会TLE？
似乎可以将$x$映射到$\frac{n}{x}$做Hash，跑得更快，至于正确性不是很清楚。
这样的时间复杂度是$O(n^{\frac{2}{3}})$？为什么呢，我也不清楚。
代码
1 |
|
