# Lời giải bài K-FACTOR

## Đề bài
Cho số nguyên dương $K$, số nguyên dương gọi là $N$ gọi là $K$-factor nếu $N$ có thể viết được bằng tích của các số nguyên dương bé hơn hay bằng $K$

Cho số $K$ và đoạn nguyên dương $[a,b]$, đếm xem trong đoạn $[a,b]$ có bao nhiêu số $K$-factor.
### Constraints
+ $2 \le K \le 10^5$
+ $1 \le a \le b \le 2 \cdot 10^9$
+ $b - a \le 2 \cdot 10^6$

## Ý tưởng

Cách tối ưu nhất để phân tích mỗi số là sử dụng thừa số nguyên tố. Giả sử ta có số $x$ như sau.
$$x = p_1^{e_1}\cdot p_2^{e_2} \cdot ... \cdot p_n^{e_n}$$
$$p_1 < p_2 < p_3 < ... < p_n$$
Số $x$ là $K$-factor khi $p_n < K$, không phải là $K$-factor khi $p_n > K$

Giả sử tồn tại vị trí $m (m \le n)$ sao cho
$$x = p_1^{e_1}\cdot p_2^{e_2} \cdot ... \cdot p_m^{e_m}\cdot ... \cdot p_n^{e_n}$$

$$p_m \le K$$

Vì $x \le 10^9$ và $b - a \le 2 \cdot 10^6$ nên ta không thể dùng sàng để phân tích thừa số nguyên tố được, hay phân tích thừa số nguyên tố trong $O(\sqrt{n})$ là quá chậm.

Dễ thấy rằng nếu $x$ là một số $K$-factor thì $\frac{x}{p_1^{e_1}\cdot p_2^{e_2} \cdot ... \cdot p_m^{e_m}} = 1$, nếu không thì giá trị $> 1$.

Với $K \le 10^5$, ta có thể dễ dàng tìm các số nguyên tố nhỏ hơn $K$ rồi chia dần $x$ cho các số nguyên tố đó thu được giá trị, rồi sẽ biết được số đó có phải là số $K$-factor hay không.

## Thuật toán

Đầu tiên ta tìm các số nguyên tố $\le K$.

Với mỗi số nguyên tố tìm được, gọi số nguyên tố hiện tại là $p$. Ta xét tất cả các bội của $p$ trong khoảng $[a,b]$. Có nhiều cách làm cho cái này.

Với mỗi bội, ta chia dần số đó cho $p$ sao cho không còn chia hết cho $p$ nữa. Ta có thể tối ưu thêm bằng cách thêm điều dừng nhỏ hơn $K$.

Ta xét lại các số đã được chia, ta bây giờ cần đếm số lượng số sau khi đã chia mà nhỏ hơn $K$ là xong.

## Code mẫu

/*
    nongvy the cutie :3
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 1e18
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define MOD (int)1e9 + 7
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    } else {
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
#endif
}
const int MAXN = 1e7 + 5;
bool sieve[MAXN + 5];
void init() {
    memset(sieve, true, sizeof(sieve));

    sieve[0] = sieve[1] = false;

    for(int i = 2; i * i <= MAXN; i++) {
        if(sieve[i]) {
            for(int j = i * i; j <= MAXN; j += i) {
                sieve[j] = false;
            }
        }
    }
}

int bs(int x, int a) {
    int l = 0, r = a;
    int res = a;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(mid * x >= a) res = mid, r = mid - 1;
        else l = mid + 1;
    }

    return res;
}

void solve()
{
    init();
    int k, a, b;
    cin >> k >> a >> b;
    vi nums;
    for(int i = a; i <= b; i++) nums.push_back(i);
    vi pr;

    for(int i = 2; i <= k; i++) {
        if(sieve[i]) pr.push_back(i);
    }

    for(int x : pr) {
        int l = bs(x, a) * x;
        while(l <= b) {
            while(nums[l - a] % x == 0 && nums[l - a] > k) nums[l - a] /= x;
            l += x;
        }
    }

    int cnt = 0;

    for(int x : nums) cnt += (x <= k);
    cout << cnt << '\n';

}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}