zcmimi's blog

arrow_back整除分块共1篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_i^n \sum_{j=i+1}^n gcd(i,j) \\\\ =\sum_i^n \sum_j^{i-1} gcd(i,j) \\\\ =\sum_d^n d \sum_i^n \sum_j^{i-1} [gcd(i,j)=d] \\\\ =\sum_d^n d \sum_i^{\frac nd} \sum_j^{i-1} [gcd(i,j)=1] \\\\ =\sum_d^n d \sum_i^{\frac nd} \varphi(i) \\\\ 于是欧拉筛加整除分块就可以了

本题为七倍经验题!!!

1/1
Search
search