题解 | 小苯的好数

#include <stdio.h>
#include <math.h>
int yingshu(int x){
    int s = sqrt(x);
    if(x!=s*s){
        return 1;
    }
    return 0;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        int n,q;
        int a[200001];
        int b[200001]={0};
        scanf("%d %d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            int g=0;
            if(a[i]%2==0||(a[i]%2==1&&yingshu(a[i])==0)){g=1;}
            b[i]=b[i-1]+g;
        }
        int l,r;
        while(q--){
            int sum=0;
            scanf("%d %d",&l,&r);
        sum=b[r]-b[l-1];
        printf("%d\n",sum);
        }
    }
}