这是一道“约数容斥”的模板题。
思路
首先先不管 $\frac{x}{g}\ne 1,\frac{y}{g}\ne 1$ 这条限制。有 gcd 的计数题的常见技巧是考虑不同的 gcd 对于答案的贡献。
我们用 $f_g(1\le g\le R)$ 表示满足 $\gcd(x,y)=g(L\le x,y\le R)$ 的数对 $(x,y)$ 的个数，用 $F_g$ 表示满足 $g|\gcd(x,y)(L\le x,y\le R)$ 的数对 $(x,y)$ 的个数。
则 $f_g=F_g-\sum\limits_{i=2}^{\left\lfloor\frac{R}{g}\right\rfloor}f_{ig}$，即 gcd 为 $g$ 的倍数的数对数量，减去 gcd 为 $g$ 的倍数但不是 $g$ 的数对数量，得到的就是 gcd 为 $g$ 的数对数量。
$F_g$ 很好求，就是所有满足 $g|x,g|y,L\le x,y\le R$ 的数对 $(x,y)$ 的数量，因此 $F_g=\left(\left\lfloor\frac{R}{g}\right\rfloor-\left\lfloor\frac{L-1}{g}\right\rfloor\right)^2$。
现在算出的答案就是 $\sum\limits_{g=2}^{R}f_g$。
最后再考虑一下 $\frac{x}{g}\ne 1,\frac{y}{g}\ne 1$ 这条限制，即 $x\ne g,y\ne g$。当 $g\lt L$ 时，由于 $L\le x,y\le R$ 这条限制，显然不存在满足条件的数对；当 $L\le g\le R$ 时，$x=g$ 和 $y=g$ 的数对分别都有 $\left\lfloor\frac{R}{g}\right\rfloor-\left\lfloor\frac{L-1}{g}\right\rfloor$ 个，$x=g$ 且 $y=g$ 的数对有 $1$ 个，因此要在刚才的答案中减去 $2\left(\left\lfloor\frac{R}{g}\right\rfloor-\left\lfloor\frac{L-1}{g}\right\rfloor\right)-1$。
最终答案为：
$$
\sum\limits_{g=2}^{R}f_g-2\left(\left\lfloor\frac{R}{g}\right\rfloor-\left\lfloor\frac{L-1}{g}\right\rfloor\right)-1
$$
算法实现&复杂度分析
计算所有 $F_g$ 的复杂度显然为 $O(R)$。
由于 $f_g$ 依赖 $f_{ig}(i\ge 2)$，所以我们倒序枚举 $g$。通过最基础的调和级数可知求出所有 $f_g$ 的复杂度为 $O(R\log R)$。
统计答案显然为 $O(R)$。
总复杂度为 $O(R\log R)$。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
cin.tie(0)->sync_with_stdio(0);
int L,R;
cin>>L>>R;
vector<ll>F(R+1);
for(int g=2;g<=R;g++){
ll o=R/g-(L-1)/g;
F[g]=o*o;
}
vector<ll>f(R+1);
for(int g=R;g>=2;g--){
f[g]=F[g];
for(int i=2;i*g<=R;i++){
f[g]-=f[i*g];
}
}// O(\sum_{i=1}^{n} \frac{n}{i}) = O(n\log n)
ll ans=0;
for(int g=2;g<=R;g++){
ans+=f[g];
if(g>=L)ans-=(R/g-(L-1)/g)*2-1;
}
cout<<ans<<endl;
return 0;
}