题解 | 小苯的好数

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

void solve(int n, int q)
{
    auto check = [](int x) -> bool
    {
        if (x % 2 == 0)
        return 1;
        int sq = sqrt(x);
        return sq * sq == x;
    };
    vector<int> pre(n + 1);
    for (int i = 1, t; i <= n; i++)
    {
        cin >> t;
        pre[i] = pre[i - 1] + check(t);
    }
    for (int i = 1; i <= q;i++)
    {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        int n1, q1;
        cin >> n1 >> q1;
        solve(n1, q1);
    }
    return 0;
}