题目大意
求出从 \(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;
}