题目大意

求出从 $l$ 至 $r$ 中满足以下条件的 $(x,y)$ 的个数。

• $\gcd(x,y) \ne 1$ 且 $\gcd(x,y)\ne x$ 且 $\gcd(x,y)\ne y$。

其中 $1\le l\le r\le 10^6$。

思路

正难则反，所以可以求出所有互质或者是相互倍数的 $(x,y)$ 的对数，在将其减去所有的方案数就是答案。

设 $s_i$ 表示满足 $\gcd(a,b)=i$ 而且 $l\le a,b\le r$ 的数对 $(a,b)$ 的个数。

因为 $\gcd(a,b)=i$，所有有 $a,b\ge i$，而且有 $i \mid a,i \mid b$。

假设满足 $x\in[l,r]$ 且 $i \mid x$ 的数量为 $num$,那么以 $i$ 为公因数的个数就是 $num\times (num-1)$。

在以上的计算中 $j\ge i$，且两数满足 $i \mid a,i \mid b$，$j \mid a,j \mid b$ 的情况在计算 $s_i$ 和 $s_j$ 的时候都会计算，所以求出的公因数而不是最小公因数。为了求出 $i$ 为最大公因数时数对的个数，$s_i$ 的计算方法应该向下面这样。

$S_i=(\lfloor r/i\rfloor-\lceil l/i \rceil)\cdot (\lfloor r/i\rfloor-\lceil l/i \rceil-1)-\sum^{\lfloor r/i\rfloor}_{j=\lceil l/i \rceil}S_{j\times i}$

其中 $s_1$ 表示 $(x,y)$ 的 $\gcd(x,y)=1$ 的数量，即 $x,y$ 互质的数量。

对于是倍数的情况，枚举每一个数 $i$，求出 $j\in[l,r]$ 且 $i \mid j$ 的所有的可能的 $j$ 的数量，将答案减去就可以了。

因为如果 $x \mid y$，那么在 $x\ne 1,y\ne 1$ 的情况下，$\gcd(x,y)=x$ 就不会与互质的情况重复计算。

时间复杂度为：

$O(\frac{r}{1}+\frac{r}{2}+\frac{r}{3}+\cdots +\frac{r}{r-2}+\frac{r}{r-1}+\frac{r}{r})=O(r \log r)$

AC Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+6;
int l,r,ans,s[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>l>>r;
	for(int i=r;i>=1;i--){
		int cnt=0,sum=0;
		for(int j=i;j<=r;j+=i){
			sum+=s[j];
			if(j>=l){
				cnt++;
			}
		}
		s[i]=cnt*(cnt-1)/2-sum;
	}
	int cnt=0;
	for(int i=max(l,2ll);i<=r;i++){
		for(int j=2*i;j<=r;j+=i){
			cnt++;
		}
	}
	int n=r-l+1;
	int ans=n*(n-1)/2;
	cout<<(ans-(cnt+s[1]))*2;
	return 0;
}