• 欢迎光临~

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

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

``````// 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;
}
``````