如何使用「构造函数法」去做Möbius反演

以前的反演都是瞎推一气直接硬推

昨天才了解到这个玩意可以构造函数搞。

那么怎么搞呢?

比如来个这个吧:

f\left( d \right) =\sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}

那么我们一般是:

f(n)= \sum_{i=1}^n{\sum_{j=1}^m{\left[ \left( i,j \right) =d \right]}}\ \left( n\geqslant m \right)

= \sum_{id=1}^n{\sum_{jd=1}^m{\left[ \left( i,j \right) =1 \right]}}

= \sum_{1\leqslant id\leqslant n}{\sum_{1\leqslant jd\leqslant m}{\sum_{g|id\ \&\ g|jd}{\mu \left( g \right)}}}

= \sum_{1\leqslant i\leqslant \frac{n}{d}}{\sum_{1\leqslant j\leqslant \frac{m}{d}}{\sum_{g|i,g|j}{\mu \left( g \right)}}}

= \sum_{1\leqslant g\leqslant \frac{m}{d}}{\mu \left( g \right) \lfloor \frac{n}{dg} \rfloor \lfloor \frac{m}{dg} \rfloor}

 

那么我们现在不这样做了,我们使用第二个反演式:

g\left( n \right) =\sum_{n|d}{f\left( d \right)}\,\,\Leftrightarrow \,\,f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) g\left( d \right)}

首先我们需要构造出一个上面所谓的 g(n) ,这里我们定义:

f\left( n \right) =\sum_{i=1}^A{\sum_{j=1}^B{\left[ \left( i,j \right) =n \right]}}

F\left( n \right) =\sum_{n|d}{f\left( d \right)}=\sum_{i=1}^A{\sum_{j=1}^B{\left[ n|\left( i,j \right) \right]}}=\sum_{i=1}^{\lfloor \frac{A}{n} \rfloor}{\sum_{j=1}^{\lfloor \frac{B}{n} \rfloor}{1}}=\lfloor \frac{A}{n} \rfloor \lfloor \frac{B}{n} \rfloor

然后呢,我们直接代进第二个反演柿子:

f\left( n \right) =\sum_{n|d}{\mu \left( \frac{d}{n} \right) F\left( d \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) F\left( nt \right)}=\sum_{t=1}^{\chi}{\mu \left( t \right) \lfloor \frac{A}{nt} \rfloor \lfloor \frac{B}{nt} \rfloor}

\left( t\xlongequal{\text{def}}\frac{d}{n},\chi \xlongequal{\text{def}}\min \left( \lfloor \frac{A}{n} \rfloor ,\lfloor \frac{B}{n} \rfloor \right) \right)

叮叮!做完啦!

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据