题目描述：
自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数
本题有多组输入数据，请使用while(cin>>)等方式处理
输入描述：
int型整数
输出描述：
n以内自守数的数量。
示例：
输入：
5
2000
输出：
3
8
说明：
对于样例一，有0，1，5，这三个自守数
解题思路：
这题是数字分析题。通过对自然数的平方数分析，来判断该自然数是否为自守数。我采用了字符串的方式进行分析，也可以用数字运算的方式，都行。代码见正常版本。
本文我主要想分享下我的提速方案，代码见提速版本。这道题目因为要多次输入，我想假如第一次输入了一个很大的数，第二次输入的数如果比上个数小，那可以直接从上个数的结果容器中快速获取答案，若比上个数大，那只需要在上个数的基础上继续往后分析即可，不需要再从头分析一遍，那样可太慢了。所以我用maxnum来表征当前已分析过的数字的最大值，每次输入新的数字，只需判断下即可，处理起来非常快。
效果对比见文末。
测试代码：
1）正常版本
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> results; bool isAN(int num) { int square=num*num; string sn=to_string(num); string ss=to_string(square); int k=ss.size()-1; for(int i=sn.size()-1;i>=0;--i) { if(sn[i]!=ss[k]) return false; k--; } return true; } int getAN(int num) { int sum=0; int k=results[results.size()-1]; for(int i=0;i<=num;++i) { if(isAN(i)) { results.push_back(i); sum++; } } return sum; } int main() { int num; while(cin>>num) { cout<<getAN(num)<<endl; } return 0; }
2）提速版本
#include <iostream> #include <vector> #include <string> #include <time.h> using namespace std; vector<int> results; int maxnum = -1; // 自守数Autonomous number bool isAN(int num) { int square = num * num; string sn = to_string(num); string ss = to_string(square); int k = ss.size() - 1; for (int i = sn.size() - 1; i >= 0; --i) { if (sn[i] != ss[k]) return false; k--; } return true; } int getAN(int num) { int sum = 0; int k; int size = results.size(); if (maxnum < num) { sum += size; for (int i = maxnum+1; i <= num; ++i) { if (isAN(i)) { results.push_back(i); sum++; } } maxnum = num; } else { for (int i = 0; i < size; ++i) { if (results[i] <= num) sum++; } } return sum; } int main() { int num; while (cin >> num) { //clock_t s, e; //s = clock(); cout << getAN(num) << endl; //e = clock(); //cout << "time:" << e - s << endl; } return 0; }
提速效果：
输入2000010、2000000、2000100、700四个数，看运行时长。
1）正常版本：
2）提速版本：
是不是提速非常的明显，代码也只稍微变换了逻辑，这就是算法的魅力。
