Cptraser/ 十月 30, 2018/ 2018.10/ 0 comments

  • \sum_{i=1}^n\sum_{j=1}^m gcd(i,j)

    \[\Rightarrow\sum_{d=1}^{min(n,m)}d\sum_{v=1}^{\frac{min(n,m)}{v}}\mu(v)\lfloor\frac{n}{dv}\rfloor\lfloor\frac{m}{dv}\rfloor\]

    \[\Rightarrow\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{d'|d}d'\mu(\frac{d}{d'})\]

    \[\Rightarrow\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\varphi(d)\]

Tips\mu \cdot id=\varphi

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*