Số đặc biệt
Xem dạng PDF
Bờm đang học về số học, cậu rất yêu thích những con số có tính chất đặc biệt. Số đặc biệt là số có đúng ~3~ ước nguyên dương.
Yêu cầu: Cho ~N~ số nguyên dương lần lượt là ~a_1, a_2, \cdots, a_N~ (~1 \leq a_i \leq 10^9~). Với mỗi số ~a_i~, cần xác định số đặc biệt ~b_i~ nhỏ nhất không nhỏ hơn ~a_i~.
Input
Dữ liệu vào: Từ tệp văn bản SDB.INP gồm ~2~ dòng.
Dòng thứ nhất chứa một số ~N~ (~1 \leq N \leq 10^6~).
Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \cdots, a_N~ (~1 \leq a_i \leq 10^9~).
Output
Kết quả: Đưa ra tệp văn bản SDB.OUT gồm ~N~ số nguyên ~b_1, b_2, \cdots, b_N~ thỏa mãn yêu cầu đề bài.
Sample Input 1
3
6 3 20
Sample Output 1
9 4 25
Sample Input 2
5
1 10 5 100 7
Sample Output 2
4 25 9 121 9
Notes
Ở test ví dụ thứ nhất:
~9~ là số nhỏ nhất không nhỏ hơn ~6~ có 3 ước nguyên dương là ~1, 3, 9~.
~4~ là số nhỏ nhất không nhỏ hơn ~3~ có 3 ước nguyên dương là ~1, 2, 4~.
~25~ là số nhỏ nhất không nhỏ hơn ~20~ có 3 ước nguyên dương là ~1, 5, 25~.
Bình luận
SOLVE:
số có 3 uoc là binh phuong một số ngto nên ta chỉ cần viết sang ngto xong push những bình phuong của những ngto đó vào 1 vector rồi với mỗi phần tử a[i] ta dung lower_bound để tìm phần tử đầu tiên có trong vector đó
code tham khảo : https://ideone.com/gwlCSX
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
include<bits/stdc++.h>
define ll long long
define N 50000
define buff iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0)
using namespace std; ll n; ll c[N+9]; void sang() { fill(c+2, c+N+1, 1); for(ll i=2; ii<=N; i++) if(c[i]==1) { for(ll j=ii; j<=N; j+=i) c[j]=0; } } ll xuly(ll x) { ll k=sqrt(x); while(1) { if(c[k]==1 && kk>=x) return kk; k++; } } int main() { ifstream cin("SDB.INP"); ofstream cout("SDB.OUT"); buff; cin>>n; sang(); while(n--) { ll x; cin>>x; cout<<xuly(x)<<" "; } return 0; }
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
CODE THAM KHẢO: https://ide.usaco.guide/ORkM31RvKtb7jYzZG20
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
tôi bị ngu
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.