DHBB 2026 - DX03 - 10 - Ước nguyên tố lẻ

Xem dạng PDF

Gửi bài giải

Điểm: 40,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trong một trường THPT, Câu lạc bộ Toán học tổ chức hoạt động chọn mã thành viên đặc biệt. Mỗi mã thành viên là một số nguyên dương ~x~.

Với mỗi số nguyên dương ~n~, gọi ~d(n)~ là số lượng ước dương của ~n~.

Một mã số ~x~ được gọi là đạt chuẩn nếu ~d(x)~ là một số nguyên tố lẻ.

Ban tổ chức đưa ra ~Q~ danh sách, mỗi danh sách tương ứng với một đoạn số ~[L, R]~. Với mỗi đoạn như vậy, hãy xác định trong các số từ ~L~ đến ~R~ có bao nhiêu mã số đạt chuẩn.

Input

  • Dòng đầu chứa số nguyên ~Q~ là số lượng truy vấn ~(1 \le Q \le 2 \cdot 10^5)~.

  • ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \le L \le R \le 10^{14})~.

  • Mỗi truy vấn yêu cầu đếm số lượng ~x~ thuộc đoạn ~[L, R]~ sao cho ~d(x)~ là một số nguyên tố lẻ.

Output

Với mỗi truy vấn, in ra trên một dòng một số nguyên là đáp án tương ứng.

Scoring

Subtask Điểm Ràng buộc
1 ~20\%~ ~Q \le 20, R \le 5000~
2 ~30\%~ ~\max(R) \le 10^7~
3 ~50\%~ Không có ràng buộc gì thêm

Sample Input 1

3
1 10
11 100
1 1000

Sample Output 1

2
5
16

Notes

Truy vấn ~[1, 10]~: các số hợp lệ là ~4 = 2^2~ và ~9 = 3^2~. Cả hai đều có đúng ~3~ ước dương.

Truy vấn ~[11, 100]~: các số hợp lệ là ~16, 25, 49, 64, 81~.

Truy vấn ~[1, 1000]~: có ~16~ số hợp lệ, gồm các bình phương của số nguyên tố không vượt quá ~1000~ và thêm hai số ~625 = 5^4~, ~729 = 3^6~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    missmphuog  đã bình luận lúc 16, Tháng 11, 2026, 16:07
    #include <bits/stdc++.h>
    using namespace std;
    
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define N 10000005
    
    const ll LIM = 100000000000000LL;
    
    vector<bool> nt(N, true);
    vector<ll> v;
    
    bool checkNT(ll n){
        if(n < 2) return false;
        for(ll i = 2; i <= n / i; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
    
    ll demUoc(ll n){
        ll ans = 1;
        for(ll i = 2; i <= n / i; i++){
            if(n % i == 0){
                int cnt = 0;
                while(n % i == 0){
                    n /= i;
                    cnt++;
                }
                ans *= cnt + 1;
            }
        }
        if(n > 1) ans *= 2;
        return ans;
    }
    
    void sang(){
        nt[0] = nt[1] = false;
    
        for(ll i = 2; i * i < N; i++){
            if(nt[i]){
                for(ll j = i * i; j < N; j += i){
                    nt[j] = false;
                }
            }
        }
    }
    
    void khoitao(){
        sang();
    
        for(ll p = 2; p < N; p++){
            if(!nt[p]) continue;
    
            ll x = p * p;
            int mu = 2;
    
            while(x <= LIM){
                if(checkNT(mu + 1)){
                    v.pb(x);
                }
    
                if(x > LIM / p) break;
    
                x *= p;
                mu++;
            }
        }
    
        sort(v.begin(), v.end());
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        //freopen("ODDDIV.INP","r",stdin);
        //freopen("ODDDIV.OUT","w",stdout);
    
        khoitao();
    
        int q;
        cin >> q;
    
        while(q--){
            ll l,r;
            cin >> l >> r;
    
            auto a = lower_bound(v.begin(),v.end(),l);
            auto b = upper_bound(v.begin(),v.end(),r);
    
            cout << b-a << '\n';
        }
    
        return 0;
    }