1. 莫比乌斯反演
首先再来简单回顾一下莫比乌斯反演
莫比乌斯函数定义如下
$$
n = p_1^{k_1}p_2^{k_2}…p_t^{k_t} \quad \mu(n) = \begin{cases} (-1) ^ t & s.t. \quad k_1=k_2=…=k_t=1 \ 0 & o.w \end{cases}
$$
莫比乌斯函数通过容斥原理可证很容易证明如下两个很重要的式子，可参考贾志鹏线性筛。
$$
n = \sum_{d|n} \phi(d) \\
[n=1] = \sum_{d|n} \mu(d)
$$
$\phi(n)$: # of x (s.t. gcd(x,n)=1 and x<=n)
莫比乌斯反演因此可以得到一条很重要的公式如下
$$
F(n) = \sum_{d|n} f(d) \Leftrightarrow f(n) = \sum_{d|n}\mu(d)F(\frac{n}{d})
$$
Proof：
$$
\begin{aligned}
f(n) &= \sum_{d|n}\mu(d)F(\frac{n}{d}) = \sum_{d|n}\mu(d)\sum_{d^{‘}|\frac{n}{d}}f(d^{‘}) \\
& = \sum_{d^{‘} | n} f(d^{‘})\sum_{d|\frac{n}{d^{‘}}}\mu(d) = \sum_{d^{‘} | n} f(d^{‘}) [\frac{n}{d^{‘}} = 1] \\
& = f(n)
\end{aligned}
$$
2. 问题描述
Count the number of distinct sequences $a_1, a_2, …, a_n (1 ≤ a_i) $consisting of positive integers such that$\gcd(a_1, a_2, …, a_n) = x$ and $\sum_{i=1}^n a_i = y$ . As this number could be large, print the answer modulo $10^9 + 7$.
简单理解就是找到序列a，满足序列上所有的数字相加等于y，且它们的gcd等于x。序列只要保证不是每一个位置上的数字都相同就是不同的序列。问这样不同的序列有多少个。(1, 2, 1和1,1,2是不同的)
这道题写出前几个答案，其实也可以在oeis上找到规律，并且上面也讲了这个答案的由来。可参考http://oeis.org/A000740。
3.问题求解
因为每个数字都必须有一个公约数x。这个问题很容易转化成n = y/x，n能组成多少个序列，保证序列和是n，且最大公约数为1。
将问题的答案定义为f(n) 。
并用g(n)表示一个数字n能组成任意多少种序列的加和。g(n)的计算就可以简单理解为将n分成n个1摆在桌上，有n-1个间隔，任意取多少个间隔，将n个1分成任意块：$g(n) = 2^{n-1}$
接下来只要寻找g(n)和f(n)的关系。g(n)中包含了所有可能形成的公约数d,用g(n,d)表示有多少种序列加和为n，且序列的最大公约数为d的序列个数。
那么$g(n) = \sum_{d|n} g(n,d) = \sum_{d|n}f(n/d) $
method 1
所以问题就很容易转化成求解
$$
f(n) = g(n) - \sum_{d|n \&d>1 } f(n/d)
$$
约数的个数实际上是很小的，当数字n越大时，约数的个数不超过n的三次方根的。接下来只要递归求解即可。利用简单的记忆化搜索思想，用map存储答案即可。给出的代码就是这样做的。
method 2
根据莫比乌斯反演转化的式子$F(n) = \sum_{d|n} f(d) \Leftrightarrow f(n) = \sum_{d|n}\mu(d)F(\frac{n}{d})$。上述的式子可以转化为莫比乌斯反演的形式：
$$
\begin{aligned}
& g(n) = \sum_{d|n} f(n/d) = \sum_{d|n} f(d) \\
\Leftrightarrow & f(n) = \sum_{d|n} \mu(d) g(n/d) = \sum_{d|n} \mu(d)2^{n/d-1}
\end{aligned}
$$
|
|
