HSG THPT Thanh Hóa 2021 - Số Đặc Biệt

Điểm: 0,30 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: BAI4.INP

Output: BAI4.OUT

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Sau khi tính toán cẩn thận, chia các đơn hàng một cách hợp lý, Thành đã mua được tất cả các món quà chỉ với số tiền là ~117649~. Mặc dù không liên quan đến việc mua bán này nhưng Thịnh nhận thấy rằng số ~117649~ rất đặc biệt, đó là nó không phải số nguyên tố nhưng lại có số các ước số dương là một số nguyên tố (số ~117649~ có đúng ~7~ ước dương), em gọi các số nguyên dương có tính chất như vậy là số "đặc biệt". Vốn rất yêu thích môn Toán và những con số, Thịnh muốn đố các bạn giải bài toán như sau:

Yêu cầu: Đếm các số "đặc biệt" trong đoạn từ ~L~ đến ~R~.

Input

Vào từ tệp văn bản BAI4.INP gồm ~2~ số nguyên dương ~L~ và ~R~ (~L \le R \le 10^{12}~).

Output

Đưa ra tệp văn bản BAI4.OUT một số duy nhất là kết quả tìm được.

Scoring

Subtask	Điểm	Giới hạn
1	~\frac{1}{3}~ số điểm	~R \le 10^5~
2	~\frac{2}{3}~ số điểm	không có ràng buộc gì thêm

Sample Input 1

2 5

Sample Output 1

Bình luận

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

porsche911 đã bình luận lúc 14, Tháng 5, 2025, 9:18 ← sửa 6 →

Cách làm cho ai bí ý tưởng nhé(sr vì giải thích hơi ngu)

{

-Khi phân tích một số thành các thừa số có dạng a1^p1 x a2^p2 x a3^p3... ( với a là số nguyên tố )
=> thì số ước của nó là (p1+1)x(p2+1)x(p3+1)x...
-Theo đề bài, số đặc biệt là số có số lượng ước là số nguyên tố:
-> số lượng ước của nó có dạng p+1 (vì số nguyên tố chỉ có một ước duy nhất là nó và 1)
-> p+1 cũng là một số nguyên tố
-Theo đề bài, số đặc biệt không phải là số nguyên tố:
-> (p+1)!=2 -> p!=1 ( trường hợp này loại bởi vì nếu a là số nguyên tố thì a^1 vẫn là số nguyên tố)
=> p+1 bao gồm các số nguyên tố lớn hơn 2
==> cách làm:
-Sàng từ 0 đến 10^7 và lưu các số nguyên tố
-Đánh dấu các số đặc biệt bé hơn 10^12 và lưu vào vector sắp xếp
-Dùng tim kiếm nhị phân để đếm số lượng số thỏa mãn trong đoạn

} {

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

long long i,j;
long long n,m;
long long k;
long long rs;
map&lt;long long,long long> f;
long long x,y,z,t;
long long page;
string s;
bool sang[10000007];
vector&lt;long long> luu;
vector&lt;long long> db;
map&lt;long long,long long> dem;
long long max12;
long long l,r;
void sangnt(long long n)
{
    fill(sang+1,sang+n+1,1);
    sang[1]=sang[0]=0;
    for(i=2;i*i<=n;i++)
    {
        if(sang[i])
        {
            for(j=i*i;j<=n;j+=i)
            {
                sang[j]=0;
            }
        }
    }
}
int main() {
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sangnt(10000007);
    for(i=2;i<=10000007;i++)
    {
        if(sang[i]) luu.push_back(i);
    }
    max12=1000000000000;
    for(i=0;i&lt;luu.size();i++)
    {
        x=luu[i];
        y=x;
        t=1;
        while(y<=max12)
        {
            if(max12/x &lt;y) break;
            y*=x;
            t++;
            if(sang[t+1])
            {
                if(dem[y]==0)
                {
                    dem[y]=1;
                    db.push_back(y);
                }
            }
        }
    }
    sort(db.begin(),db.end());
    cin>>x>>y;
    r=upper_bound(db.begin(),db.end(),y)-db.begin();
    l=lower_bound(db.begin(),db.end(),x)-db.begin();
    cout<&lt;max(0LL*0,r-l);
}

}

-2

quannmq2009 đã bình luận lúc 23, Tháng 4, 2025, 3:48

cho mình hỏi có phải chỉ có số chính phương mới có số ước dương là số lẻ => kiểm tra các số chính phương có số ước là nguyên tố trong đoạn [L,R] là đc có đko vậy

0

HUNG2010 đã bình luận lúc 12, Tháng 5, 2025, 14:45

Sao mình thấy bạn qua contest nào cũng nhắn xàm xàm hết vậy

-7

trinhminhduc9b đã bình luận lúc 21, Tháng 8, 2024, 6:04

output la 4: 2 3 4 5

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

TrungHieu_HL đã bình luận lúc 5, Tháng 6, 2024, 1:55

không test đúng đấy chỉ có các số không là các số nguyên tố và có số ước là số nguyên tố mới đúng

-1

AI đã bình luận lúc 26, Tháng 5, 2024, 9:58 ← chỉnh sửa →

-5

khnguyen21th06 đã bình luận lúc 18, Tháng 5, 2024, 9:58

sao mình nhẩm thì lại là 2 3 4 5 v ạ?, output sai đk?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

2

DinhVantung0611 đã bình luận lúc 24, Tháng 6, 2024, 6:47

"không phải số ng tố" nhưng có số ước số dương là số ng tố. TH input chỉ có số 4 ok thôi

-1

nguyenhuynh663459 đã bình luận lúc 16, Tháng 5, 2024, 3:54

bài này khó quá ai chỉ với

-3

tranvantrongghgvnb đã bình luận lúc 7, Tháng 5, 2024, 1:38

mình tưởng out là phải 3 số chứ nhỉ : 2 3 5