题意：

自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数

解法（循环加判断）

枚举从0~n所有数字，分别判断每个数字是否满足条件即可。

具体的，我们假设当前枚举到数字 $i$

我们设变量 $x=i,y=i^2$

由于数字 $i$ 是非负数，显然 $bit(y)>=bit(x)$ ，其中bit(x)表示数字x在十进制下的位数

我们按照『数字翻转』的while循环写法来写，循环条件为 $x>0$ ，每次分别取出当前x和y的个位，即 $x mod10$ 和 $ymod10$ ，要满足在循环中每次取出的个位都相等，即可把答案+1

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        int ans=1;//数字0肯定满足，故答案初始设置为1
        for(int i=1;i<=n;i++){//从1开始枚举
            int x=i;//当前数字
            int y=i*i;//平方数字
            bool flag=true;//标记是否满足条件
            while(x>0){
                if(x%10!=y%10){
                    flag=false;//如果有一位不相等，则退出
                    break;
                }
                x/=10;
                y/=10;
            }
            if(flag)ans++;//答案+1
        }
        cout<<ans<<endl;
    }
    return 0;
}

时间复杂度： $O(nlog_{10}n)$ ，我们需要从小到大枚举n个数字，对于每一个数字，我们需要将数字在十进制下的每一位拆开，复杂度是 $O(log_{10}n)$ ，故总的时间复杂度为 $O(nlog_{10}n)$

空间复杂度： $O(1)$ ，程序中没有开额外的数组，也没有递归调用，故空间复杂度为 $O(1)$

题解 | #自守数#

题意：

解法（循环加判断）