gcd.

题意

给出 T 组数据，每组给出 l, r, x。
要求计算：

gcd(floor(l/x), floor((l+1)/x), ..., floor(r/x))

思路

先看一个可以直接验证想法的朴素解：

直接从 i = l 枚举到 r，把每个 floor(i/x) 算出来，然后一路求 gcd。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int T;
ll l, r, x;

ll gcd_ll(ll a, ll b) {
    while (b != 0) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void solve_one() {
    ll ans = 0;
    for (ll i = l; i <= r; i++) {
        ll v = i / x;
        if (ans == 0) {
            ans = v;
        } else {
            ans = gcd_ll(ans, v);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> l >> r >> x;
        solve_one();
    }

    return 0;
}

这个做法只适合小数据，因为 l, r 可以到 10^18。

关键观察是：floor(i/x) 随着 i 增大，只会保持不变或者加 1，所以区间里的这些值一定是若干个连续整数，可能带重复。

例如 l=7, r=16, x=2 时：

i	7	8	9	10	11	12	13	14	15	16
floor(i/2)	3	4	4	5	5	6	6	7	7	8

从这张表可以看出，一旦区间跨过两个不同的整除块，就一定会同时出现两个相邻整数，比如这里的 3 和 4。
而相邻整数的 gcd 一定是 1，所以整段的 gcd 也只能是 1。

因此只需要看两端：

若 floor(l/x) = floor(r/x)，说明整段值都相同，答案就是这个值；
否则，区间一定出现相邻整数，答案直接是 1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int T;
ll l, r, x;

void solve_one() {
    ll left = l / x;
    ll right = r / x;

    if (left == right) {
        cout << left << '\n';
    } else {
        cout << 1 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> l >> r >> x;
        solve_one();
    }

    return 0;
}

复杂度

每组数据只做常数次运算，时间复杂度是 $O(1)$ ，空间复杂度是 $O(1)$ 。

总结

这题的核心不是求 gcd，而是看清 floor(i/x) 的分段常值结构。

同块时全都相等；跨块后一定出现相邻整数，所以答案只可能是：

公共值；
或 1。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析