2021 陕西省赛 C - GCD // 整除分块

题目来源：2021年ICPC国际大学生程序设计竞赛暨陕西省第九届大学生程序设计竞赛

题目链接：https://ac.nowcoder.com/acm/contest/35232/C

题意

给定三个整数 \(l\)、\(r\)、\(k\)，求 \(\sum_{i = 1}^{r}f(i)\).

当可以在 \([l,r]\) 中找到 \(k\) 个数 \(\{ a_1, a_2, ..., a_k \}\)， 使得 \(gcd(a_1, a_2, ..., a_k) = i\) 成立时，\(f(i) = 1\)；否则，\(f(i) = 0\).

数据范围：\(1 \le l,r \le 10^{12}\)，\(2 \le k \le r - l + 1\).

思路：整除分块

\(f(i) = 1\) 的充要条件为：\([l,r]\) 中存在至少 \(k\) 个 \(i\) 的倍数，即 \(\lfloor \frac{\large r}{\large i} \rfloor - \lfloor \frac{\large l-1}{\large i} \rfloor \ge k\).

我们知道，\(\lfloor \frac{\large n}{\large i} \rfloor\) 这个式子的值是呈块状分布的，于是可以分别对 \(\lfloor \frac{\large r}{\large i} \rfloor\) 、\(\lfloor \frac{\large l-1}{\large i} \rfloor\) 找出这些块（（\(\lfloor \frac{\large r}{\large i} \rfloor\) 相等的块、\(\lfloor \frac{\large l-1}{\large i} \rfloor\) 相等的块），那么就可以双指针扫一遍，求出一个个的公共块（ \(\lfloor \frac{\large r}{\large i} \rfloor\) 、\(\lfloor \frac{\large l-1}{\large i} \rfloor\) 都相等的块），如果满足限制就将块长统计进答案里。

更简单的，整除分块时，可以对两个式子同时做，直接找出的就是公共块。

时间复杂度：\(O(\sqrt{l} + \sqrt{r})\).

代码

// Two Pointer Version
#include <bits/stdc++.h>
#define endl '\n'
#define LL long long
using namespace std;

LL L, R, k;

struct Block {
    LL l, r, k;
};

vector<Block> v1, v2;

void get(vector<Block>& v, LL n)
{
    for(LL l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        v.push_back({ l, r, n / l });
    }
}

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

    cin >> L >> R >> k;

    get(v1, L - 1), v1.push_back({ L, R, 0 });
    get(v2, R);

    LL ans = 0;
    int n = v1.size(), m = v2.size();
    for(int i = 0, j = 0; i < n && j < m; ++ i) {
        while(v1[i].r > v2[j].r && j < m) {
            LL l = max(v1[i].l, v2[j].l), r = min(v1[i].r, v2[j].r);
            if(v2[j].k - v1[i].k >= k) {
                ans += r - l + 1;
            }
            ++ j;
        }
        if(j == m) break;
        LL l = max(v1[i].l, v2[j].l), r = min(v1[i].r, v2[j].r);
        if(v2[j].k - v1[i].k >= k) {
            ans += r - l + 1;
        }
        if(v1[i].r == v2[j].r) ++ j;
    }

    cout << ans << endl;

    return 0;
}

// Easy Version
#include <bits/stdc++.h>
#define endl '\n'
#define LL long long
using namespace std;

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

    LL L, R, k;
    cin >> L >> R >> k;

    LL ans = 0;
    for(LL l = 1, r; l <= R; l = r + 1) {
        if(l <= L - 1) r = min((L - 1) / ((L - 1) / l), R / (R / l));
        else r = R / (R / l);
        if(R / l - (L - 1) / l >= k) ans += r - l + 1;
    }
    cout << ans << endl;

    return 0;
}