• 题意
• 题解
• 代码

原题地址：GCD

题意

给你l, r和k，在l到r中任意取k个数，所有取法他们对应的最大公约数一共有多少个数。

1 ≤ l ≤ r ≤ 10^12，2 ≤ k ≤ r - l + 1

题解

看似是要求所有最大公约数，其实是让求所有可能的公约数。
证明：设任意一个数m = i * j是区间[l, r]内的两个数x，y的最大公约数，那么x与x + i的最大公约数即为i，x与x + j的最大公约数即为j。即所有可能的公约数都可以是题意里的最大公约数。

而判断一个数x是否是[l, r]内的某k个数的公约数，可以用式子r/x - (l-1)/x ≥ k来判断。

要遍历每个x是不可能的，这里采用整除分块的方法将时间复杂度降为O(\(\sqrt{n}\))。
整除分块：对于任意的i，满足n/i == n/j的最大的j为n/(n/i)。利用这个结论可以很轻易地算出\(\sum\limits_{i = 1}^{n}{n \over i}\)

for (LL l = 1, r; l <= n; l = r + 1) {
	r = n / (n / l);
	ans += (r - l + 1) * (n / l);
}

利用整除分块思想即可得出解题代码

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define _for(i, n) for(LL i = 1, lennn = n; i <= lennn; i++)
#define rep(i, a, b) for(LL i = a, lennn = b; i <= lennn; i++)
#define per(i, a, b) for(LL i = a, lennn = b; i >= lennn; i--)
#define sc(x) scanf("%lld", &x)
#define pf(x) printf("%lld\n", x)
#define pu push_back
#define po pop_back
#define maxn 1000006
#define maxnn 1000000007
#define mp make_pair
LL a[maxn], ma = -1, mi = maxnn;

void sol() {
    LL ans = 0;
    LL l, r, k;
    cin >> l >> r >> k;
    for(LL i = 1, j; i <= r; i = j + 1) {
        if (i < l) j = min(r / (r / i), (l - 1) / ((l - 1) / i));
        else j = r / (r / i);
        ans += (j - i + 1) * ((r / i - (l - 1) / i) >= k);
    }
    pf(ans);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    time_t t1 = clock();
#endif

    
    sol();

#ifndef ONLINE_JUDGE
    printf("time:%.2lfms\n", 1000.0 * (clock() - t1) / CLOCKS_PER_SEC);
#endif
    return 0;
}