终于完全看懂一次题解……
然后自己按照理解再写一发~
· 题意 #传送门#
(Tab. 原题目经分析得到……)
给出 $n,m$ ,求 $\sum_{i=1}^n\sum_{j=1}^m2\gcd(i,j)-1$ 。
· 解析
因为 $m,n$ 比较大,不难想到用数论解决。又因为 gcd 与莫比乌斯反演有密不可分的联系,所以从这个角度想可能会 easy 一些~
推导的过程如下:
〇 不妨假设 $n<m$ ;
① 先把求和里的式子化简一下:
$ $令 $g=\gcd(i,j)$,那么我们就要求 “$\sum_{i=1}^n\sum_{j=1}^mg$”;
② 根据反演的结论 “$n=\sum_{d|n}\phi(n)$” ,我们把它代入式子,可得:
③ 按照套路把枚举 $d$ 的求和拿到外面来:
④ 不难由 $i\in[1,n]$ , $j\in[1,m]$ 想到满足 $d|i$ 的 $i$ 的取值有 $\left\lfloor\frac{n}{d}\right\rfloor$ 个,满足 $d|j$ 的 $j$ 的取值有 $\left\lfloor\frac{m}{d}\right\rfloor$ 个;则:
现在预处理出 $\phi()$ (线性筛),然后枚举就可以了~
· 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~