题目传送门(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);}