关于gcd的博文已经写过三篇了,为什么还要写呢?(任意中文输入法下输入gcd)你就懂了0.0
计算 $f(n) = \sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)==1]$
这里给出 $f(n)$ 的两个计算公式。
$$
n^2 = \sum_{d=1}^n \sum_{i=1}^{n} \sum_{j=1}^n [gcd(i,j)==d] =
\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i,j)==1] = \sum_{d=1}^n f(\lfloor \frac{n}{d} \rfloor)
$$
因此由之前的博文可用记忆化搜索的方法求出$f(n)$
$$
f(n) = \sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)==1] =
\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{d|i,d|j} \mu(d) = \sum_{d=1}^n \mu(d) (\lfloor \frac{n}{d} \rfloor)^2
$$
因此由博文 在预处理后可根号算法快速求出。
实际上,$f(n)$ 还有一个表达式。
$$ f(n)= 2 \sum_{i=1}{n} \phi(i) - 1 $$
为什么两个完全不同的式子都可以计算呢。实际上这是由广义Dirchilet 性质决定的。
hdu5663一个更复杂的例子
计算 $r(n,m)=\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j))$,其中$f(n)=0$ 若 $n$ 是平方数,否则为 $1$。
解:我们不妨设 $n \leq m$。
$$
\begin{aligned}
r(n,m) &=\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j)) \\
&= \sum_{d=1}^n f(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum_{t|i,t|j} \mu(t) \\
&= \sum_{d=1}^n f(d) \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \lfloor \frac{n}{dt} \rfloor \lfloor \frac{m}{dt} \rfloor \\
&= \sum_{G=1}^n \lfloor \frac{n}{G} \rfloor \lfloor \frac{m}{G} \rfloor \sum_{t|G} \mu(t)f(\frac{G}{t})
\end{aligned}
$$
据此,我们可以给出下面代码。(上面过程技巧性很强,要充分利用 $\mu$ 的强大力量)
1 | //#pragma comment(linker,"/STACK:10240000,10240000") |