题目的主要信息：

• 自守数是指一个数的平方的尾数等于该数自身的自然数
• 请求出n以内的自守数的个数，包括0包括n

方法一：取模验证法

具体做法：

首先0必定是自守数，算作初始为1。我们可以遍历1到n，验证每个数$ii$是否是自守数，如果它是自守数，那么$i^{2}i^2$对$ii$这么多位零的整十整百或者整千整万数取余就会得到$ii$本身，因此我们可以在遍历的时候初始取模为10，每当$ii$等于模将其扩大十倍即可。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 1; //0属于自守数
        int base = 10; //取余基数
        for(int i = 1; i <= n; i++){
            int x = i * i;
            if(i == base) //保证每次取余与i的位数相同
                base *= 10;
            if(x % base == i) //取余后是否等于i
                count++;
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历，从1到$nn$，每次验证都是常数时间
• 空间复杂度：$O(1)O(1)$，常数空间

方法二：字符串比较法

具体做法：

首先0必定是自守数，算作初始为1。我们可以遍历1到n，验证每个数$ii$是否是自守数，验证的时候我们将数字转变成字符串，然后查看二次方字符串末尾的子串是否和原数字相等，如果相等则是自守数，否则不是。

#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 1; //0属于自守数
        string s;
        string pows;
        for(int i = 1; i <= n; i++){
            s = to_string(i); //将数字转成字符串
            pows = to_string(i * i);
            if(pows.substr(pows.length() - s.length()) == s) //比较平方字符串末尾是否等于i
                count++;
        }
        cout << count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历，从1到$nn$，每次验证都是常数时间，因此字符串长度是常数
• 空间复杂度：$O(1)O(1)$，常数空间，字符串长度是常数