c++ - 找到给定范围内的完美正方形的数量

Question

我试图找出给定范围内的完美正方形的数量。我遵循的方法提供于:digital_root

我实现的代码有时没有给出正确答案，因为此方法没有考虑 10,1000 等数字。

请帮我想出这个方法。

 int cot=0;
void squares(int a,int b){
    if(a==b){
        int digit,digit_root=0,no;
        no=a;
        digit=no%10;
        if(digit==2||digit==3||digit==7||digit==8){
        }else{
            no=a;
            while(no>0){
            digit=no%10;
            if((digit==0)||(digit==9)){

            }else{
                digit_root=digit_root+digit;
                digit_root=digit_root%9;
            }
            no=no/10;
    }
            if(digit_root==0||digit_root==7||digit_root==1||digit_root==4){
                if(digit_root==1){
                    if(a)
                }
                cot++;
            }
        }

        }else{
        int c=(a+b)/2;
        squares(a,c);
        squares(c+1,b);
    }


}

int main() {
   int a,b,t;
    cin>>t;
    for(int i=0;i<t;i++){
     cin >> a>>b;
    squares(a,b);   
        cout << cot<<endl;
        cot=0;
    }

    return 0;
}

Answer 1

最好的算法可能是减去 sqrt(bigger number) - sqrt(other num)，也就是像这样

int a = 1,b=100;
if (sqrt(a) != int(sqrt(a)){
    cout<<int(sqrt(b))-int(sqrt(a))<<endl;}
else{
    cout<<int(sqrt(b))-int(sqrt(a))+1<<endl;}

逻辑很简单，完全平方就是自然数*同一个自然数所以，1*1,2*2,3*3,4*4等等

所以你只需要得到较大数字的最接近完美平方根并用较小数字减去它(小心以防最小数字本身是完美平方)