网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF1575G
2024-08-22
CF1575G GCD Festival 题解
考虑欧拉反演\[\sum\limits_{d\midn}\varphi(d)=n\]则原式可以化为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(a_i,a_j)\cdot\gcd(i,j)\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(a_i,a_j)\sum\li