• 欢迎光临~

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

开发技术 开发技术 2022-11-26 次浏览

题目来源: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;
}
程序员灯塔
转载请注明原文链接:2021 陕西省赛 C - GCD // 整除分块
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com