2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

目录

1001 ^&^
1002 array
1003 K-th occurrence
1004 path
1005 huntian oy
1006 Shuffle Card
1007 Windows Of CCPC
1008 Fishing Master
1009 Kaguya
1010 Touma Kazusa‘s function
1011 sakura

1006 huntian oy

队友知道后面那串东西当a,b互质的时候就是i-j，那么变成求 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j)[gcd(i,j)==1]\) 。

要求：
\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j)[gcd(i,j)==1]\)

很明显把i提前：
\(\sum\limits_{i=1}^{n}i\varphi(i)\space - \space \sum\limits_{j=1}^{i}j[gcd(i,j)==1]\)

后面那个是求：
\(\sum\limits_{i=1}^{n}i[gcd(i,n)==1]\)

显然：
\(\sum\limits_{i=1}^{n}i[gcd(i,n)==1] = \frac{n}{2}([n==1]+\varphi(n))\)

代进去得到：
\(\sum\limits_{i=1}^{n}i\varphi(i) - \frac{i}{2}([i==1]+\varphi(i))\)

即：
\(-\frac{1}{2}+\frac{1}{2}\sum\limits_{i=1}^{n}i\varphi(i)\)

这个是卷个g=id就可以得到了。

原文：https://www.cnblogs.com/Inko/p/11402622.html