@description@
定义F(n)表示最小公倍数为n的二元组的数量。
即：如果存在两个数（二元组）X，Y(X <= Y)，它们的最小公倍数为N，则F(n)的计数加1。
例如：F(6) = 5，因为[2,3] [1,6] [2,6] [3,6] [6,6]的最小公倍数等于6。
给出一个区间[a,b]，求最小公倍数在这个区间的不同二元组的数量。
例如：a = 4，b = 6。符合条件的二元组包括：
[1,4] [2,4] [4,4] [1,5] [5,5] [2,3] [1,6] [2,6] [3,6] [6,6]，共10组不同的组合。
@solution@
将 [X, Y] 变为 [1, Y] - [1, X-1]，将无序对转有序对，处理一下相等的情况。
那么就是求 (sum_{i=1}^{n}sum_{j=1}^{n} [frac{i imes j}{gcd(i, j)} leq n])。套路反演一波得到：
记 f(m) 表示 abc <= m 对应的有序对 (a, b, c) 数量。可以用杜教筛等方法做（不过貌似过不了），但是还有一个更有趣的做法：
我们不妨假设 a <= b <= c，然后根据里面 a, b, c 互相之间的相等关系算这样的无序对的贡献。
那么显然有 (a leq m^{frac{1}{3}}, b leq sqrt{frac{m}{a}})。然后暴力在范围内枚举 a, b 即可。
算一个 f(m) 时间复杂度为 (O(sum_{i=1}^{m^{frac{1}{3}}}sqrt{frac{m}{i}}))，简单积分拟合一下可以算出大概是 (O(n^{frac{2}{3}}))。
然后外层枚举莫比乌斯函数，总时间复杂度为 (O(sum_{i=1}^{sqrt{n}}(frac{n}{i^2})^{frac{2}{3}}))。这玩意儿不定积分原函数在 x = 0 没有定义，不过我们可以直接代 x = 1（因为是从 1 ~ (sqrt{n})），结果算出来还是 (O(n^{frac{2}{3}}))。
@accepted code@
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1000000;
bool nprm[MAXN + 5];
int prm[MAXN + 5], mu[MAXN + 5], pcnt;
void init() {
mu[1] = 1;
for(int i=2;i<=MAXN;i++) {
if( !nprm[i] ) prm[++pcnt] = i, mu[i] = -1;
for(int j=1;i*prm[j]<=MAXN;j++) {
nprm[i*prm[j]] = true;
if( i % prm[j] == 0 ) {
mu[i*prm[j]] = 0;
break;
}
else mu[i*prm[j]] = -mu[i];
}
}
}
ll get(ll m) {
ll ans = 0;
for(ll i=1;i*i*i<=m;i++) {
for(ll j=i;i*j*j<=m;j++) {
ll lb = j, ub = m / i / j;
ans += (j == i ? 3 : 6)*max(0LL, ub - lb);
ans += 3*(j != i);
}
ans++;
}
return ans;
}
ll solve(ll n) {
ll ans = 0;
for(ll i=1;i*i<=n;i++)
ans = ans + mu[i] * get(n / i / i);
return (ans + n) / 2;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll d[MAXN + 5];
int main() {
init();
ll a, b; scanf("%lld%lld", &a, &b);
printf("%lld
", solve(b) - solve(a - 1));
}
@details@
莫比乌斯反演的应用分析（×）
积分在时间复杂度分析中应用（√）
不要想着 cmath 库里面的 pow 函数的精度，直接把 (a leq n^{frac{1}{3}}) 转变成 (a^3 leq n)。