题解 | #自守数#
自守数
http://www.nowcoder.com/practice/88ddd31618f04514ae3a689e83f3ab8e
题意：
自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数
解法（循环加判断）
枚举从0~n所有数字，分别判断每个数字是否满足条件即可。
具体的，我们假设当前枚举到数字
我们设变量
由于数字是非负数，显然%3E%3Dbit(x))
，其中bit(x)表示数字x在十进制下的位数
我们按照『数字翻转』的while循环写法来写，循环条件为
，每次分别取出当前x和y的个位，即
和
，要满足在循环中每次取出的个位都相等，即可把答案+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;
}
时间复杂度：
空间复杂度：)
，程序中没有开额外的数组，也没有递归调用，故空间复杂度为
我现在也只有一个保底
太难了
查看15道真题和解析
蓝月亮公司福利 72人发布