查看原题
点击跳转设f_i
表示所有数\gcd
为i
还要加入的数的期望数量
ans=1+\frac{\sum_{i=1}^mf_i}m
可以知道f_1=0
f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)
继续推式子:
\begin{aligned}
f_i
&=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\
&=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m
\end{aligned}
把分子拿出来
\begin{aligned}
&\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\
&=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\
&=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\
&=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\
&=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\
\end{aligned}\\
设T=dx
=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor
带入原来的式子
f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m
设F_T=\sum_{d|T} f_d \mu(\frac Td)
当d\not = i
时可以每算出一个f_i
就更新所有F_x(i|x)
当d=i
时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1
f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m
\\
f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m
\\
f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m
\\
f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}
这样就可以先算f_i
,再算F_i
了
[d\not=i]
这个条件只在T=i
的时候才有限制
枚举到T=i
,计算f_i
时,F_x(x<i)
都已经计算好了
F_i
还少了f[i] \times \mu(1)
这正好是要剪掉的部分