Tóm tắt đề bài: Cho ~T~ số nguyên, với mỗi số nguyên, xuất ra màn hình YES nếu số đó có số ước là chẵn, xuất ra NO nếu ngược lại.

Subtask ~1~:

• Với mỗi ~x_i~, ta đếm ước của nó trong ~O(\sqrt{x_i})~.
• Đpt: ~O(T \times \sqrt{x})~
• Code tham khảo:

bool ok(long long x) {
    int cnt = 0;
    for (int i = 1; i*i <= x; i++) {
        cnt += 2 - (n/i == i);
    }
    return cnt%2 == 0;
}

int main() {
    int t; cin >> t;
    while (t--) {
        long long x; cin >> x;
        cout << (ok(x) ? "YES" : "NO") << '\n';
    }
}

Subtask ~2~:

• Một số nguyên chỉ có số ước là lẻ khi và chỉ khi đó là số chính phương. Đến đây bài toán đã trở thành kiểm tra xem ~x_i~ có phải số chính phương hay không. Ta có thể thực hiện kiểm tra trong ~O(1)~ bằng cách kiểm tra căn của nó có phải số nguyên hay không.
• Đpt: ~O(T)~.
• Code tham khảo:

int main() {
    int t; cin > t;
    while (t--) {
        long long x, tmp; cin >> x;
        tmp = sqrt(x);
        cout << (tmp*tmp == x ? "YES\n" : "NO\n");
    }
    return 0;
}