SP8496 NOSQ - No Squares Numbers 题解

这道题可以用到前缀和思想，先预处理出所有的结果，然后 \(O(1)\) 查询即可。

注意：

是不能被 \(x^2(x≠1)\) 的数整除的数叫做无平方数。
\(d\) 可以为 \(0\)。

即对于每次询问，给出 \(s[b][d]-s[a-1][d]\) 的值。

#include<cstdio>

#include<iostream>

using namespace std;

int s[100005][10];//第s[i][j]位存储从0~i中包含j的无平方数的数量

int t;

int a,b,c;

int z,p;

bool find(int x){

    for(int i=2;i*i<=x;i++){//注意i=2而非i=1，如原解释注意

        if(x%(i*i)==0) return false;

    }

    return true;

}

int main(){

    for(int i=2;i<=100000;i++){

        if(find(i)){

            z=i;

            while(z){

                p=z%10;

                s[i][p]=1;

                z/=10;

            }

        }

    }

    for(int i=0;i<=9;i++){

        for(int j=2;j<=100000;j++){

            s[j][i]+=s[j-1][i];

        }

    }

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d",&a,&b,&c);

        printf("%d\n",s[b][c]-s[a-1][c]);

    }

    return 0;

}

巴特西

SP8496 NOSQ - No Squares Numbers 题解

最新文章

热门文章