昨天刚说完不搞数论了，刚看到一个(gcd)的题目dalao用这个做了，虽然比正解麻烦，还是打算学一学了
数论函数：
数论函数的定义：
数论函数亦称算术函数，一类重要的函数，指定义在正整数集上的实值或复值函数，更一般地，也可把数论函数看做是某一整数集上定义的函数
常见积性函数
(mu(n))
(~~~~~~~~n=1:mu(n)=1)，(n=prodlimits_{i=1}^k p_i:mu(n)=(-1)^k)，(d)有任何质因子幂次大于等于(2:mu(n)=0)
(d(n))
(~~~~~~~~n)的约数个数
(sigma(n))
(~~~~~~~~n)的约数和函数
(varphi(n))
(~~~~~~~~)小于等于(n)且与其互质的个数
完全积性函数
(epsilon(n))
(~~~~~~~~epsilon(n)=[n=1])
(I(n))
(~~~~~~~~I(n)=1)恒等函数
(id(n))
(~~~~~~~~id(n)=n)
卷积：
设(f(x),g(x))是两个数论函数（以自然数集为定义域的复数值函数），则卷积运算(f*g)定义为：
((fast g)(n) = sum_{dmid n}{f(d)g(frac{n}{d})})
当然还有另一种更直观的写法：
((fast g)(n) = sum_{ij=n}{f(i)g(j)})
函数的一些简单性质：
交换律：
((f * g)(n) = (g * f)(n))
证明：这不显然的嘛
结合律：
(egin{align} ((fast g)ast h)(n) &= (fast (gast h))(n) end{align})
(egin{align} ((fast g)ast h)(n) &= sum_{lk=n}(fast g)(l)h(k) \ &= sum_{lk=n}left(sum_{ij=l}f(i)g(j) ight)h(k)\ &= sum_{ijk=n} f(i)g(j)h(k) end{align})
(egin{align} (fast (gast h))(n) &= sum_{il=n}f(i)(gast h)(l) \ &= sum_{il=n}f(i)left(sum_{jk=l}g(j)h(k) ight)\ &= sum_{ijk=n} f(i)g(j)h(k) end{align})
莫比乌斯函数性质一
(sum_{d|n}mu(d)=[n=1])
证明：
将(n)分解： (n=P_1^{a_1} imes P_2^{a_2} ...... P_k^{a_k})
不需要考虑(a_k>1)的情况，因为定义当((a_k>1))时，(mu(a_k)=0)
只需要化成幂为(1)，(m=P_1 imes P_2 imes P_3 imes P_4... imes P_k)
这样的话问题就变成了从k个因数中取奇数个和偶数个的种数的差的值是否为-1 可以很快的列出
莫比乌斯函数性质二
(dfrac{varphi(x)}{n}=sumlimits_{d|n} dfrac{mu(d)}{d})
先来推倒一个简单的式子((mu*I)=epsilon)
((mu*I)(n)=sumlimits_{d|n}mu(d)I(dfrac{n}{d}))
(~~~~~~~~~~~~~~~=sumlimits_{d|n}mu(d))
(~~~~~~~~~~~~~~~=[n=1])
(~~~~~~~~~~~~~~~=epsilon)
同理，下面的式子也是这个道理
证明：
(ecause varphi*I=id Rightarrow varphi*I*mu=id*mu Rightarrow varphi * epsilon=id*mu)
( herefore varphi=id*mu Rightarrow varphi(n)=sumlimits_{d|n}mu(d)id(dfrac{n}{d}))
证毕：( herefore dfrac{varphi(x)}{n}=sumlimits_{d|n} dfrac{mu(d)}{d})
莫比乌斯反演
满足函数
(~~~~~~~~~~F(n)=sum_{d|n}f(d))
那么存在
(~~~~~~~~~~f(n)=sum_{d|n}mu(d)F(lfloorfrac{n}{d} floor))
证法：
(sum_{d|n}mu(d)F(lfloorfrac{n}{d} floor)=sum_{d|n}mu(d)sum_{i|lfloorfrac{n}{d} floor}f(i))
(~~~~~~~~~~~~~~~~~~~~~~~~~~~=sum_{i|n}f(i)sum_{d|lfloorfrac{n}{i} floor}mu(d)) 利用性质一，当(i=n)时，后项才为(1)
(~~~~~~~~~~~~~~~~~~~~~~~~~~~=f(n))
反过来莫比乌斯反演还有另一种形式
满足函数
(~~~~~~~~~~F(n)=sum_{n|d}f(d))
那么存在
(~~~~~~~~~~f(n)=sum_{n|d}mu(frac{d}{n})F(d))