HSG THPT Thanh Hóa 2021 - Số Đặc Biệt
Xem dạng PDF
Gửi bài giải
Đ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ả:
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
1
Bình luận
có ai có cách làm đơn giản hơn không ạ
include<bits/stdc++.h>
using namespace std;
define ll long long
ll nhan(ll p,ll q) { ll res=1; while(q>0) { if (q%2!=0) { res=p; } p=pp; q/=2; } return res; } vector<ll>p; vector<ll>q; const int nmax=1000000; bool nt[nmax+5]; void sang() { memset(nt,true,sizeof(nt)); nt[0]=nt[1]=false; for(int i=2;i<=sqrt(nmax);i++) { if (nt[i]) { for(int j=i*i;j<=nmax;j+=i) { nt[j]=false; } } } for(int i=2;i<=50;i++) { if (nt[i]) q.pushback(i); } for(int i=2;i<=nmax;i++) { if (nt[i]) p.pushback(i); } } int main () { freopen("BAI4.inp","r",stdin);freopen("BAI4.out","w",stdout); ios::syncwithstdio(0);cin.tie(0);cout.tie(0); ll l,r; cin>>l>>r; sang(); ll t=0; vector<ll>a; for(ll i:p) { for(ll j:q) { if(j==2) continue; t=nhan(i,j-1); if (t<=1e12) { a.push_back(t); } } } sort(a.begin(),a.end()); a.erase(unique(a.begin(), a.end()), a.end());
}
code đơn giản cho ng ms
include<bits/stdc++.h>
define ll long long
define N int(1e6)
define str string
define el '\n'
using namespace std; bool prime[N+2]; vector<int>v; void sang(){ memset(prime,true,sizeof(prime)); prime[0]=prime[1]=0; for (int i=2;ii<=N;i++){ if (prime[i]){ for (int j=ii;j<=N;j+=i) prime[j]=0; } } for (int i=2;i<=N;i++) v.pushback(i); } bool check(ll n){ if (n<2) return false; if (n<=N) return prime[n]; if (n%2==0||n%3==0)return false; for (int i=5;i*i<=n;i+=6) { if (n%i==0||n%(i+2)==0) return false; } return true; } bool kt(int n){ int s=1; for (int i=0;v[i]*v[i]<=n;i++){ int p=v[i]; int t=0; while(n%p==0){ t++; n/=p; } s*=2*t+1; } if (n>1) s*=3; if (check(s)) return true; return false; } int main(){ iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); freopen("BAI4.inp","r",stdin); freopen("BAI4.out","w",stdout); sang(); ll a,b; cin>>a>>b; ll m=sqrt(a); if (mm!=a) m++; int res=0; for (ll i=m;ii<=b;i++){ if (kt(i)) res++; } cout<<res; return 0; }
Cách làm cho ai bí ý tưởng nhé(sr vì giải thích hơi ngu)
{
} {
}
Sàng giống sàng phân đoạn ạ?
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
Sao mình thấy bạn qua contest nào cũng nhắn xàm xàm hết vậy
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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
-_-
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
"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
bài này khó quá ai chỉ với
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.