Số đặc biệt

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: SDB.INP
Output: SDB.OUT
Author:
bedao
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~.

Comments

Please read the guidelines before commenting.


  • 0
    thiendanh0909  commented on Dec. 29, 2025, 1:55 p.m.

    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


  • -6
    sb_anhtuan  commented on Dec. 5, 2025, 8:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 1
    dphuc02040608  commented on Sept. 23, 2025, 5:05 p.m.

    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; }


  • 4
    Groot  commented on Aug. 3, 2025, 7:13 p.m.

    Lần đầu thấy rõ sức mạnh thực sự của ios_base::sync_with_stdio(false); cin.tie(nullptr);, mình code nếu không thêm vào thì KHÔNG THỂ pass được test nào @@!!


  • -3
    hohoanghai5042011  commented on July 14, 2025, 12:51 a.m. 
    #include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int i,j,n,l,r,m;
long long a[N],ans;
bool s[N];
int p[N],t;

void sangnt(){
    for(i=0;i<N;i++) s[i]=1;
    s[0]=s[1]=0;
    for(i=2;i*i<N;i++)
        if(s[i])
            for(j=i*i;j<N;j+=i)
                s[j]=0;
    for(i=2;i<N;i++)
        if(s[i])
            p[t++]=i;
}

long long f(long long x){
    l=0,r=t-1;
    while(l<=r){
        m=(l+r)/2;
        if(1LL*p[m]*p[m]>=x){
            ans=1LL*p[m]*p[m];
            r=m-1;
        }
        else l=m+1;
    }
    return ans;
}

int main(){
    ifstream cin("SDB.INP");
    ofstream cout("SDB.OUT");
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    sangnt();
    for(i=1;i<=n;i++) cout<<f(a[i])<<" ";
    return 0;
}

    • 0
      HoangHK15CKG  commented on Feb. 13, 2026, 10:34 a.m. ← edit 3

      thỉnh thoảng có 1 test quá thời gian bạn ơi


  • -8
    haanhphat2010  commented on July 5, 2025, 5:47 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    HUNG2010  commented on June 2, 2025, 12:01 p.m.

    CODE THAM KHẢO: https://ide.usaco.guide/ORkM31RvKtb7jYzZG20


  • -4
    tien_phat  commented on May 8, 2025, 3:38 p.m.

    https://www.ideone.com/yEe9KA


  • -34
    nguyenducanhhc  commented on April 13, 2025, 3:25 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    K32NGHIEMDUNG  commented on April 11, 2025, 5:08 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -5
      TNLB25102009  commented on July 21, 2025, 3:46 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -48
      nguyenducanhhc  commented on April 13, 2025, 3:26 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -7
        lamnhb111  commented on Aug. 8, 2025, 12:22 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.