最终得对抗自己

[BZOJ 2671]Calc 莫比乌斯函数

题目大意

给出N,统计满足下面条件的数对(a,b)的个数:
1.1≤a<b≤N
2.a+b整除a*b

解题报告

首先这道题的复杂度是不对的…

反正能过qwq。

我觉得这位dalao的题解写得非常妙啊, 当然同时安利一下看我的题解…

首先考虑题目给出的条件, \((a+b)|ab\)
设\(d=gcd(a,b)\), 那么有:$$ \frac{a+b}{d} | \frac{ab}{d} $$

接下来证明当\( a \)和\(b\)互质时, \(a+b\)和\(ab\)互质:

设\(a\)和\(b\)互质且\(a+b\)和\(ab\)有公共质因子\(k\), 那么有\(k|a\)或者\(k|b\)。
假设\(k|a\)那么可得$$a=qk \Rightarrow a+b = qk+b \Rightarrow k|(qk+b) \Rightarrow k|b \Rightarrow k|gcd(a,b)$$
假定不成立, \(a+b\)和\(ab\)必须互质。

继续化简条件, 设\(a=\frac{a}{d}, b=\frac{b}{d}\):
$$ (a+b) | abd $$
由(a+b)和ab互质可得:
$$ (a+b) | d $$

由于\(b*d\le N \)并且\((a+b)|d\), 所以\(b\le m, m=\sqrt{N}\), 题目等价于统计:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}[gcd(a, b) == 1]\lfloor \frac{N}{b(a+b)} \rfloor $$

接下来利用莫比乌斯函数进行化简关键一步!
根据莫比乌斯函数性质有$$ (\sum_{d|n}\mu(d)) = [n == 1] $$
那么用这个性质代替gcd(a, b)等于1的约束, 化成:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}(\lfloor \frac{N}{b(a+b)} \rfloor \sum_{d|gcd(a, b)}\mu(d)) $$
枚举\(gcd(a, b)\)因子\(d\), 设\(a=d\cdot a, b=b\cdot d\), 将后面一坨提前:
$$ \sum_{d=1}^m \sum_{b=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{a=1}^{b-1} \lfloor \frac{N}{d^2b(a+b)} \rfloor $$
最后一坨\(\lfloor \frac{N}{d^2b(a+b)} \rfloor\)只有\(\sqrt{N}\)种取值, 分段计算, 暴力搞就可以了。

代码

   

加入讨论

电子邮件地址不会被公开。 必填项已用*标注

关于本站

这是Hineven的博客!
主要保存蒟蒻的解题报告(笔记)
还有发布分享一些奇怪的东西

你可以通过上面的↑友情链接
访问Socialists的其他博客。

The Socialists!

我们的Site:socialists.studio
访问量:

AmazingCounters.com