[HSG-QH_TPHT_HT_24] Số chính phương

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên (chẳng hạn ~0, 1, 4, 9~ là các số chính phương; ~3, 7, 10~ không phải là số chính phương).

Cho số nguyên dương ~N~ và dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~.

Yêu cầu

Tìm số chính phương nhỏ nhất không xuất hiện trong dãy đã cho.

Dữ liệu đầu vào

Gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~;
  • Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ ~(0 \le a_{i} \le 10^{12},\ i = 1, 2, ..., N)~ các số ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên là kết quả tìm được.

Ràng buộc dữ liệu

  • Có 40% test ứng với 40% số điểm có ~N \le 10^3,\ 0 \le a_{i} \le 10^3~;
  • Có 30% test ứng với 30% số điểm có ~10^3 < N \le 10^6,\ 0 \le a_{i} \le 10^6~;
  • Có 30% test ứng với 30% số điểm có ~10^3 < N \le 10^6,\ 10^6 \le a_{i} \le 10^{12}~;

Ví dụ

Ví dụ 1
INPUT
5
1 9 2 0 16
OUTPUT
4

Bình luận

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


  • 0
    hoanglan_nd_502  đã bình luận lúc 4, Tháng 1, 2026, 13:13

    bài này đẹp trai mới ăn may submit ac đc nha ae

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    unordered_set<ll> mp;
    for (int i=0;i&lt;n;i++){
        ll x;
        cin>>x;
        mp.insert(x);
    }
    for (ll i=0;;i++){
        if (mp.find(i*i)==mp.end()){
            cout<&lt;i*i;
            return 0;
        }
    }
    return 0;
}

  • -4
    nguyenminhquang_vp_906  đã bình luận lúc 4, Tháng 12, 2024, 10:53

    hi ae


  • -2
    nguyendanhduong_vp_526  đã bình luận lúc 3, Tháng 12, 2024, 3:09

    chúc anh em 8386