CF1780E题解

· · 题解

前置知识：整除分块。

先分析题目性质。

首先，根据题意，保存下来的边权中有 x 当且仅当存在两个数 l\leq i<j\leq r,\gcd(i,j)=x。

如果存在一组解 (i,j)，则 (i,i+x) 必然也是一组解。因为 x|i,x|j,x|i+x，可得 l\leq i<i+x\leq j\leq r；类似于 \gcd(i,i+1)=1，x|i 时可得 \gcd(i,i+x)=x。

另外，x|i 不仅是 \gcd(i,i+x)=x 的充分条件，也是必要条件，可以简单地通过反证法证明。

所以，保存下来的边权中有 x 当且仅当存在 l\leq i<i+x\leq r,x|i 。

也就是说，[l,r] 间存在至少两个 x 的倍数。

即： \lfloor \frac{r}{x}\rfloor\geq\lfloor \frac{l-1}{x}\rfloor+2。

注意到 l\leq10^9，考虑对 x\leq l-1 的情况整除分块。

（x\geq l 的情况不是不行，但是我们稍后再说。）

设 [a,b] 是一个极大区间，满足 \lfloor \frac{l-1}{a}\rfloor=\lfloor \frac{l-1}{b}\rfloor=d 。

则要求出 [a,b] 范围内的满足 \lfloor \frac{r}{x}\rfloor\geq d+2 的 x 数量。

可得 $\frac{r}{d+2}\geq x$， 即$x\leq\lfloor\frac{r}{d+2}\rfloor$。 所以 $x$ 的上界为 $\min(b,\lfloor\frac{r}{d+2}\rfloor)$。 这部分的代码如下： ```cpp ll l, r; scanf("%lld %lld", &l, &r); l--; // 方便处理l-1 ll ans = 0; for(ll a = 1, b; a <= l; a = b + 1) { ll d = l / a; b = l / d; ans += max(min(b, r / (d + 2)) - a + 1, 0ll); } ``` 再说 $x\geq l$ 的情况。 此时 $\lfloor \frac{l-1}{x}\rfloor=0$，故 $\lfloor\frac{r}{x}\rfloor\geq2

可得 x\leq\lfloor\frac{r}{2}\rfloor。

这部分的代码：

l++; // 把l-1还原成l
ans += max(r / 2 - l + 1, 0ll);

完整代码：

#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

void MAIN()
{
    ll l, r;
    scanf("%lld %lld", &l, &r);
    l--; // 方便处理l-1
    ll ans = 0;
    for(ll a = 1, b; a <= l; a = b + 1)
    {
        ll d = l / a;
        b = l / d;
        ans += max(min(b, r / (d + 2)) - a + 1, 0ll);
    }
    l++; // 把l-1还原成l
    ans += max(r / 2 - l + 1, 0ll);
    printf("%lld\n", ans);
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T--)
        MAIN();
    return 0;
}