NOI2016 循环之美


Solution

设分子为 \(x\) 分母为 \(y\) ,\((x,y)=1\),循环节长度为 \(l\) ,那么有 \(xk^l \equiv x \models y \leftrightarrow k^l \equiv 1 \models y \leftrightarrow (k,y)=1\)

那么变成求 \[ \begin{aligned} &\sum_{i=1}^m\sum_{j=1}^n [(i,j)=1][(i,k)=1] \\ &=\sum_{d=1}^{m}\sum_{i=1}^{m/d}\sum_{j=1}^{n/d}\mu{(d)}[(id,k)=1] \\ &=\sum_{d=1}^{m}\sum_{i=1}^{m/d}\sum_{j=1}^{n/d}\mu{(d)}[(i,k)=1][(d,k)=1] \\ &=\sum_{d=1}^{m}[(d,k)=1]\mu{(d)}\sum_{i=1}^{m/d}\sum_{j=1}^{n/d}[(i,k)=1] \\ &=\sum_{d=1}^{m}[(d,k)=1]\mu{(d)}\frac{n}{d}\sum_{i=1}^{m/d}[(i,k)=1] \end{aligned} \] 看起来很能整除分块 先想一想后面那个和式,如果 \(m/d <=k\) 那么我们可以预处理,如果大于 \(k\) 的话可以直接整除再乘上 \(\phi(k)\) ,因为 \((i+nk,k)=(i,k)\)。那么这部分就已经可以快速乘了。 现在只要能求 \(\sum_{d=1}^{m}[(d,k)=1]\mu{(d)}\) 就能整除分块了。来演一演。

\[ \begin{aligned} &\sum_{d=1}^{m}[(d,k)=1]\mu{(d)} \\ &=\sum_{g \mid k}\mu{(g)}\sum_{d=1}^{m/g}\mu{(gd)} \\ &=\sum_{g \mid k}\mu{(g)}^2\sum_{d=1}^{m/g}\mu{(d)}[(g,d)=1] \end{aligned} \] 出现了递归。 \(S(m,k)=\sum_{d \mid k}\mu{(g)}^2S(m/g,g)\) 递归的终点是 \(m<=1\) or \(k=1\) 。只要杜教筛一下就能求啦,再用map记录加速一下就可以了。


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录