Hướng dẫn giải

Cho số nguyên dương ~N \le 10^6~, đếm và liệt kê tất cả các số chính phương nhỏ hơn hoặc bằng ~N~. In ra số lượng ở dòng đầu, các số chính phương ở dòng thứ hai.

Cách làm

Số chính phương là bình phương của một số nguyên, ví dụ ~1, 4, 9, 16, \dots~. Ta thử lần lượt các số ~i = 1, 2, 3, \dots~ và dừng khi ~i \times i > N~.

Đầu tiên, một vòng lặp đếm số lần ~i \times i \le N~ để in số lượng. Sau đó, một vòng lặp thứ hai in các giá trị ~i \times i~ cách nhau một khoảng trắng.

Vì ~N~ có thể lớn tới ~10^6~ nên ta dùng kiểu ~long long~ cho ~i~ để tích ~i \times i~ không bị tràn.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    // Đếm số chính phương: i*i <= n thì i*i là số chính phương không lớn hơn n
    int dem = 0;
    for (long long i = 1; i * i <= n; i++) {
        dem++;
    }
    cout << dem << "\n";
    // In các số chính phương từ nhỏ đến lớn, cách nhau một khoảng trắng
    for (long long i = 1; i * i <= n; i++) {
        if (i > 1) {
            cout << " ";
        }
        cout << i * i;
    }
    cout << "\n";
    return 0;
}