BZOJ 2005 [Noi2010] 能量采集

发布于 2017-05-18  267 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2005

题意:(0,0) 到 (x,y) 连线上整点数*2-1 的和.... 1 ≤ x ≤ n , 1 ≤ y ≤ m

 


结论是对于点 (i,j),与原点的连线经过的整数点的数量是 gcd(i,j)... 证明是比较显然的... 扩欧

那么就有下式....\(Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)\),即\(Ans=2*\sum_{i=1}^{n}\sum_{j=1}^{m} gcd(i,j)-m*n\)

那么要求的就是\(\sum_{i=1}^{n}\sum_{j=1}^{m} gcd(i,j)\) 了... 方法很多,欧拉函数,莫比乌斯反演据说都可以... 今天又学习了一个好方法 (奇技淫巧

我们令 f[i] 为 gcd(x,y)=i 的数对数,那么怎么求 f[i] 呢?在 1 ≤ x ≤ n, 1 ≤ y ≤ m 中,满足 gcd(x, y) | d 的 (x,y) 有 [n/d] * [m/d] 个。但是这是有重复的,哪些重复了呢?d 的倍数重复了...

怎么解决呢?倒着搞再减掉即可... 这样做代码很短,比较优雅,为什么说是奇技淫巧呢... 因为复杂度是\(O(nlog_n)\) 的.....

WA 点在注释中体现了

那么代码如下:

 


一个非常弱的准退役OIER