Given integers l, r, and k, determine how many distinct greatest common divisors (GCDs) can be formed by selecting any k numbers from the range [l, r].

The constraint is: 1 ≤ l ≤ r ≤ 10^12, 2 ≤ k ≤ r - l + 1.

Rather than computing all possible GCD values directly, we count all potential divisors. Any integer m = i × j that divides two numbers x, y within [l, r] can serve as their GCD. For instance, if x and x+i share GCD i, and x and x+j share GCD j, then both i and j qualify as valid GCD candidates.

To verify whether an integer x serves as a common divisor among at least k elements in [l, r], use the condition:

$$ \left\lfloor \frac{r}{x} \right\rfloor - \left\lfloor \frac{l-1}{x} \right\rfloor \geq k $$

Direct iteration over each x would be inefficient. Enstead, apply integer division block technique wich reduces complexity to O(√n). This method leverages the property that for fixed n/i, the maximum value of j satisfying n/i = n/j equals n/(n/i).

Using this principal efficiently calculates sums like:

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

Here's the implementation tailored to solve the problem:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve() {
    ll result = 0;
    ll left, right, count;
    cin >> left >> right >> count;
    
    for(ll start = 1, end; start <= right; start = end + 1) {
        if (start < left) 
            end = min(right / (right / start), (left - 1) / ((left - 1) / start));
        else 
            end = right / (right / start);
            
        ll total_multiples = right / start - (left - 1) / start;
        result += (end - start + 1) * (total_multiples >= count);
    }
    cout << result << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    return 0;
}