题目传送门(BZOJ)
>原文链接<

题解 :

对于一个坐标(x, y), 我们要知道k = \gcd(x, y)-1

证明 :

\gcd(x, y) = t, 则x=at, y = bt,

所有在这条直线上的整数点坐标为(a, b), (2a, 2b), (3a, 3b)\cdots(ta, tb)t个,

又因为(x, y)不算在内, 所以是t-1\gcd(x, y)-1

(x, y)损耗就是2\times \gcd(x, y)-1

所以原题就变成了求这个式子 :

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(\gcd(i, j)\times 2-1)

= 2\times \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)-n\times m

需要处理的就只有\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)

\sum\limits_{d|n}\varphi(d) = n

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i, j)}\varphi(d)

枚举d

\sum\limits_{d=1}^{n}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[d|i,d|j]\varphi(d)

n范围内, d|i的数量是\lfloor\frac{n}{d}\rfloor

故枚举总量不变, 原式可化为 :

\sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\varphi(d)

所以直接\sqrt n+\sqrt m分块求和, 线筛预处理S_\varphi即可

代码 :

#include<iostream>#include<cstring>#include<cstdio>using namespace std;#define ll long longconst int N = 1e5+5;bool np[N];ll n, m, ans;ll phi[N], pr[N];inline void init() { phi[1] = 1; for(int i = 2; i <= n; i ++ ) { if(!np[i]) { pr[++*pr] = i; phi[i] = i-1; } for(int j = 1; j <= *pr&&i*pr[j] <= n; j ++ ) { np[i*pr[j]] = 1; if(i%pr[j] == 0) { phi[i*pr[j]] = phi[i]*pr[j]; break; } else phi[i*pr[j]] = phi[i]*(pr[j]-1); } phi[i] += phi[i-1]; }}int main() { scanf("%lld%lld",&n,&m); if(n>m) swap(n,m); init(); for(ll i = 1,lst; i <= n; i = lst+1) { lst = min(n/(n/i),m/(m/i)); ans += (ll)(phi[lst]-phi[i-1])*(n/i)*(m/i); } printf("%lld\n",ans*2-n*m);}