【题意】给定a和b，求满足a<=lcm(x,y)<=b && x<y的数对(x,y)个数。a,b<=10^11。
【算法】莫比乌斯反演+组合计数
【题解】★具体推导过程参考：51nod1222 最小公倍数计数
过程运用到的技巧：
1.将所有i和j的已知因子提取出来压缩上届。
2.将带有μ(k)的k提到最前面，从而后面变成单纯的三元组形式。
最终形式：
$$ans=\sum_{k=1}^{\sqrt n} \mu(k) \sum_{d} \sum_{i} \sum_{j} [i*j*d<=\frac{n}{k^2}]$$
问题转化为枚举(d,i,j)三元组满足其乘积<=n/k^2。
虽然题目要求组合（有序），但是有d的存在，所以先求排列（无序）。
但是三元组的排列不方便统计，所以求三元组的组合乘上排列系数
先算严格从小到大的，然后减去两个相同的和三个相同的。
最后+n后/2就变成组合。
听说复杂度O(n^(2/3))。
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int maxn=;
int miu[maxn],prime[maxn],tot;
bool vis[maxn];
int solve(int x){
if(!x)return ;
int N=(int)sqrt(x)+,ans=;
for(int k=;k<=N;k++)if(miu[k]){
int n=x/(k*k);
for(int d=;d*d*d<=n;d++){
for(int i=d+;i*i*d<=n;i++)ans+=miu[k]*((n/(d*i)-i)*+);
ans+=miu[k]*((n/(d*d)-d)*+);
}
}
return (ans+x)/;
}
#undef int
int main(){
#define int long long
int A,B;
scanf("%lld%lld",&A,&B);
int N=(int)sqrt(B)+;
miu[]=;
for(int i=;i<=N;i++){
if(!vis[i]){miu[prime[++tot]=i]=-;}
for(int j=;j<=tot&&i*prime[j]<=N;j++){
vis[i*prime[j]]=;//
if(i%prime[j]==)break;
miu[i*prime[j]]=-miu[i];
}
}
printf("%lld\n",solve(B)-solve(A-));
return ;
}