求(sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}d(ij))
不知道怎么讲.....
首先考虑(d(ij))究竟是什么
首先,很自然地想到,既然是求(ij)的约数个数
因此就枚举(i,j)的约数
即(d(ij) =sumlimits_{x|i}sumlimits_{y|j}...)
注意到,我们不能重复地统计
我们从唯一分解得形式来考虑
因为多个质因子个和一个质因子的情况是一致的
因此我们考虑一个质因子
假设(i = p^a, j = p^b)且(aleq b)
那么对于(ij = p^{a+b}),它的约数中质因子的取值范围为([0,;;a+b])
如果我们能制定一种规则使得每个质因子取值只与一种(i,j)的质因子方案对应就好了
记当前枚举的(ij)约数为(d),且(d = p^c = p^{a'+b'}),其中(a')来源于(i),(b')来源于(j)
注意到,对于([0,;;b]),我们都可以只让(a' = 0, b' = [0,b])来达到
而([b+1,;;a+b]),我们可以只让(a'=[1,a], b' = b)来达到
而(b'=b)相当于(b'=0)(枚举因子的特殊性)
也就是说(a'=0)或(b'=0)时对应一种情况
也就是只要判断([gcd(i, j)=1])即可
因此(d(ij) = sumlimits_{x|i}sumlimits_{y|j} [gcd(x, y)=1])
那么,简单地化下式子,答案就能出现
$sumlimits_{i=1}^{n} sumlimits_{j=1}^{m} d(ij) = sumlimits_{i=1}^{n} sumlimits_{j=1}^{m} sumlimits_{x|i} sumlimits_{y|j} [gcd(x, y)=1] $
(=sumlimits_{i=1}^{n} sumlimits_{j=1}^{m} sumlimits_{x|i} sumlimits_{y|j} sumlimits_{d|x ;and ;d|y} mu(d))
注意到,我们如果先枚举(d),相当于枚举它的倍数(i, j),再枚举(i, j)内有多少数含(d)因子
(=sumlimits_{d=1}^{min(n,m)} mu(d)sumlimits_{d|i}^{n} sumlimits_{d|j}^{m} [n/ d][m/d])
预处理(mu)以及某个神奇的函数就可以回答了