https://www.luogu.org/problemnew/show/P2568

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

一开始还以为要莫比乌斯反演.

推了半天不知道怎么求,遂看题解:

$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} [gcd(i,j)==p] = \sum\limits_{i=1}^{\frac{n}{p}}\sum\limits_{j=1}^{\frac{n}{p}} [gcd(i,j)==1] $

首先一个数跟他自己的gcd是质数的条件就是他自己就是质数,否则我们考虑一个有序数对 \((i,j),(i>j)\) 与 \(i\) 互质的数的个数也就是 \(\varphi(i)\) ,

那么答案就是 $2*\sum\limits_{i=1}^{n}\varphi(i) + \sum\limits_{i=1}^{n}[i==p] $