题目链接：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 点在注释中体现了

那么代码如下：