题解 | 小苯的好数

=解题思路
1. 判断好数：一个数是好数当且仅当它是偶数或完全平方数。对每个数用 `sqrt` 并调整误差后判断是否为完全平方数。
2. 转换数组：将原数组转换为 0/1 数组，1 表示好数，0 表示不是好数。
3. 前缀和：预处理前缀和数组 `prefix[i]` 表示前 i 个数中好数的个数。
4. 回答询问：区间 `[l, r]` 的好数个数 = `prefix[r] - prefix[l-1]`，O(1) 时间输出。
#include <stdio.h>
#include<math.h>

#define MAX 200001

int goodnum(long long x){
    if(x%2==0){
        return 1;
    }
    long long r=(long long)sqrt(x);
    
    while(r*r>x)r--;
    while(r*r<x)r++;
    return (r*r==x);
}

int main() {
    
    
    int n,q;

    int times;
    scanf("%d",×);
    while(times--){
    scanf("%d %d",&n,&q);

    int x=1;
    long long y,num;
    int a[MAX];
    for(int i = 1; i <= n; i++) {
        long long num;
        scanf("%lld", &num);
        a[i] = goodnum(num);
    }
        
    int l,r,index;
    int prefix[MAX]={0};
    
        
    for(int i=1;i<=n;i++){
        
        prefix[i]=prefix[i-1]+a[i];        
        
    }
    for(int m=0;m<q;m++){
        scanf("%d %d",&l,&r);
        printf("%d\n",prefix[r]-prefix[l-1]);
    }}


    return 0;
}