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
các bạn cho mình hỏi là tại sao code của mình lại không AC với ạ mình check mãi không ra
include <bits/stdc++.h>
define notthing ios::syncwithstdio(false), cin.tie(0), cout.tie(0);
define ll long long
define theend return 0;
using namespace std;
vector<bool> snt(4e4 + 1, true); vector<ll> a; void sang() { snt[0] = snt[1] = false; for(ll i = 2; i <= 4e4; i++) { if(snt[i]) { a.push_back(i); for(ll j = i * i; j <= 4e4; j += i) snt[j] = false; } } } /// sàng số nguyên tố + tạo mảng tìm kiếm
int main() { notthing sang(); ll n; cin >> n; while(n--) { ll x; cin >> x; ll s = sqrt(x); if(s * s < x) s++; ll m = *lower_bound(a.begin(), a.end(), s); /// tìm kiếm số phù hợp cout << m * m << " "; /// in ra kết quả } theend }
đây là code của mình nhé WA 100% mình cũng không hiểu tại sao
Lỗi của bạn là bạn chưa nhập xuất file cho bài này trong khi bài có yêu cầu. Bạn có thể thấy là ở phần "Input" và "Output" ở trên đề và ở bên phải màn hình, ngay dưới chỗ "Time limit" và "Memory limit" có ghi rõ.
Để nhập xuất file bạn thêm đoạn code sau
yeahhh cảm ơn bạn rất nhiều nhé tôi đã AC rồi!!!
Đây là một lỗi cơ bản mà nhiều người mắc phải do vô tình quên nhưng thường để lại hậu quả lớn. Nên khi làm bài, nếu mà thấy file thì nhớ viết lệnh vô luôn nhé.
Để mà có thể sử dụng terminal trên IDE code mà khi nộp lên vẫn có thể mở file thì bạn dùng lệnh sau
bài này đáng nhẽ xử lý offline
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; }
thỉnh thoảng có 1 test quá thời gian bạn ơi
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
https://www.ideone.com/yEe9KA
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.
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.