Nhận xét

• Số lần lật quả trứng thứ ~n~ sẽ bằng số ước của ~n~
• Vì trạng thái ban đầu của quả trứng là ngửa, nên nếu số lần lật là lẻ, quả trứng sẽ ở trạng thái úp xuống. Ngược lại, quả trứng sẽ ở trạng thái ngửa.
• Chỉ các số chính phương mới có số ước là số lẻ. Các số không phải số chính phương có số ước là số chẵn.

Cách làm

• Subtask 1: Vì ~n~ khá nhỏ nên ta sinh một mảng ~a[n]~ có các giá trị ban đầu bằng 0. Với các giá trị từ ~1~ đến ~n~, phần tử nào trong mảng chia hết cho ~n~ thì biến đổi phần tử đó. Độ phức tạp ~\mathcal{O}(n^2)~
• Subtask 2: Dùng 1 vòng for để đếm số ước của ~n~. Nếu số ước là số chẵn thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(\sqrt{n})~
• Subtask 3: Chúng ta sẽ cải tiến subtask 2. Xét ~n~ có phải số chính phương hay không. Nếu ~n~ là số chính phương thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(1)~

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = 55;
long long n;
void solve()
{
    cin >> n;
    for(int i=2 ; 1LL*i*i*i <= n ; ++i)
    {
        if(n%i == 0)
        {
            int k = 0;
            while(n%i == 0) 
            {
                ++k;
                n /= i;
            }
            if(k&1)
            {
                cout << 0 << '\n';
                return;
            }
        }
    }
    if(n == 1)
    {
        cout << 1 << '\n';
        return;
    }
    int tmp = sqrt(n);
    if(1LL * tmp * tmp == n)
    {
        cout << 1 << '\n';
        return;
    }
    cout << 0 << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}