最近刷莫反题目,刷着刷着,发现problem b这道题目可以用三种方法推出来,觉得记下来以后可以方便复习,也算巩固一下。
不一定更好的阅读体验:https://blog.csdn.net/m0_51990674/article/details/120069090
problem b
这类问题是:
$$
\sum_{i = 1} ^ n \sum_{j = 1}^m[gcd(i , j) = d]
$$
关于这个问题,我们再熟悉不过,答案是:
$$ \sum_{d’ = 1}^{min(\frac{n}{d} , \frac{n}{d})} \mu(d’)[\frac{n}{d\*d’}]\*[\frac{m}{d\*d’}] $$
推法一(容斥原理):
考虑经典转换:
$$
\sum_{i = 1} ^ n \sum_{j = 1}^m[gcd(i , j) = d] = \sum_{i = 1} ^ n \sum_{j = 1}^m[gcd(i / d , j / d) = 1]\tag{1}
$$
上式我们还可以套用一个经典变换。
$$ \sum_{i = 1} ^ n \sum_{j = 1}^m[gcd(i / d , j / d) = 1]= \sum_{i = 1} ^ {\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}}[gcd(i , j ) = 1] \tag{2} $$
即:考虑$1$到$n/d$,$1$到$m / d$中,有多少个数对满足互质的个数。
很明显,互质的个数 = 总数 - 不互质的个数.
不互质的个数是几个呢?
我们考虑枚举倍数,2的倍数的个数,3的倍数的个数,4的倍数的个数..考虑符号的时候,发现和莫比乌斯函数的符号是一致的,这个以前的博客证明过,在这不啰嗦。与$(n/d) * (m/d)$ 合并后得答案:
$$ \sum_{i = 1}^{min(n , m)}[\frac{n}{d\*i}] \* [\frac{m}{d\*i}] \* \mu(i)\tag{3} $$
推法二(根据莫比乌斯函数性质):
由莫比乌斯函数性质可得:
$$ \sum_{i = 1} ^ {\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}}[gcd(i , j ) = 1] =\sum_{i = 1} ^ {\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}}\sum_{d’ | gcd(i , j)}\mu(d’)\tag{4} $$
$d’$是$gcd(i , j)$的因子,我们观察到前面两个求和只是在修饰$\mu$,给$\mu$提供一个范围,我们还发现:$d’$实际上可以取到$1 \sim min(\frac{n}{d},\frac{m}{d})$,这个很容易想明白:如果$i , j$一样,那么最大共因子是他的本身,所以$1 \sim min(\frac{n}{d},\frac{m}{d})$的范围内,$d’$都可以取到。
现在我们要思考的是:每个$\mu(d’)$被枚举了多少次?我们什么时候能取到这个$d’$呢,答案是当$i , j$是$d’$的倍数的时候,$gcd(i , j)$是$d’$的倍数。答案呼之欲出:
$[\frac{n}{d\*d’}] \* [\frac{m}{d\*d’}]$
$$ \sum_{d’ = 1}^{min(\frac{n}{d} , \frac{n}{d})}\mu(d’)[\frac{n}{d\*d’}] \* [\frac{m}{d\*d’}]\tag{5} $$
根据我们严谨的分析,$(4)与(5)$等价。
推法三(莫比乌斯反演):
莫比乌斯反演:
若
$$ F(n) = \sum_{n | d}f(d)\tag{6} $$
则
$$ f(n) = \sum_{n | d}\mu(\frac{d}{n})F(d)\tag{7} $$
对于本题:
我们设:
$$ F(d) = \sum_{i = 1}^{n}\sum_{j = 1} ^ {m}[d | gcd(i , j )]\tag{8} $$
$$ f(d) = \sum_{i = 1}^{n}\sum_{j = 1} ^ {m}[gcd(i , j ) = d]\tag{9} $$
很明显$(8)(9)$满足$(6)$,那么我们可以根据$(7)$式子直接列出:
$$ f(n) = \sum_{n | d}\mu(\frac{d}{n})\sum_{i = 1}^{n}\sum_{j = 1} ^ {m}[d | gcd(i , j )]\tag{10} $$
为了不引起歧义,原来的n , m改为a , b
我们发现:$d/n$是枚举的从$1\sim n$的自然数,我们将$d/n$设为$d’$则:
$$
f(n) = \sum_{d’}\mu(d’)\sum_{i = 1}^{a}\sum_{j = 1} ^ {b}[d’n | gcd(i , j )]\tag{11}
$$
根据推$(5)$式的方法,我们推出:
$$ f(n) = \sum_{d’ = 1}\mu(d’)\sum_{i = 1}^{a}\sum_{j = 1} ^ {b}[d’n | gcd(i , j )]\tag{12} $$
$$ f(n) = \sum_{d’ = 1}\mu(d’)[\frac{a}{d’\*n}][\frac{b}{d’\*n}] \tag{13} $$
答案显而易见:
$$ f(d) = \sum_{d’ = 1}\mu(d’)[\frac{a}{d’\*d}][\frac{b}{d’\*d}]\tag{14} $$
通过三种方法:我们发现推出的式子完全一样。殊途同归说的便是这吧。我觉得这也是数论的魅力。代码略。
好哎!