自守数
描述
自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数。本题有多组输入数据
示例1
输入：5
2000
输出：3
8
说明：对于样例一，有0，1，5，这三个自守数
2000
输出：3
8
说明：对于样例一，有0，1，5，这三个自守数
方法一：
思路分析
本题读完后的直接的思路是给定一个数，先求解出它的位数或者叫长度，然后将其平方的后面对应位数求出，比较两者的大小，如果两者值相等，那么这个数是自守数，这也是根据自守数的定义直接计算的
图解
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
核心代码
#include <bits/stdc++.h>
using namespace std;
int get_length(int x);
int get_tail(int x,int count_i);
int main()
{
int n=0;
while(cin>>n)
{
if(n==0) cout<<0<<endl;
else if(n==1) cout<<2<<endl;
else
{
int count=2;
for(int i=2;i<=n;i++)
{
int count_i=get_length(i);//计算i的位数
int sq_i=i*i;//i的平方
if(count_i==get_length(sq_i)) continue;//如果i与i的平方长度相等，则直接判定不是自守数
int tail=get_tail(sq_i,count_i);//计算i的平方后面对应的几位数
if(i==tail)
count++;
}
cout<<count<<endl;
}
}
return 0;
}
int get_length(int x)//计算整数的长度/位数，例如25有两位
{
int leng=0;
while(x)
{
x/=10;
leng++;
}
return leng;
}
int get_tail(int x,int count_i)//计算整数的后面几位数
{
int tail=0;
for(int i=0;i<count_i;i++)
{
int mod_i=x%10;
x=x/10;
tail+=mod_i*pow(10,i);//例如25*25=625，则计算625后面两位数=25
//cout<<i<<" "<<mod_i<<" "<<10^i<<" "<<tail<<endl;
}
return tail;
}
复杂度分析
- 时间复杂度：该算法的时间主要在计算一个整数的长度以及整数平方的后面几位，因此总的时间复杂度为$O(n)$
- 空间复杂度：空间复杂度为$O(1)$
方法二
思路分析
方法一中有许多不必要的工作，例如求解一个整数的位数，其实只要直接比较整数与其平方，方法为：每次模10得到的余数是否相等，然后更新整数和整数的平方为模10得到的值，直到整数为0（整数必然要比其平方数小）
核心代码
#include <bits/stdc++.h>
using namespace std;
int Automorphic_number(int sq_i,int i);
int main()
{
int n;
while(cin>>n)
{
if(n==0) cout<<0<<endl;
else if(n==1) cout<<2<<endl;
else
{
int count=2;
for(int i=2;i<=n;i++)
{
int sq_i=i*i;
if(Automorphic_number(sq_i, i)==1)
count++;
}
cout<<count<<endl;
}
}
return 0;
}
int Automorphic_number(int sq_i,int i)
{
while(i)//只需判断i,因为i<sq_i
{
if(sq_i%10!=i%10)
return 0;
else
{
sq_i=sq_i/10;
i=i/10;
}
}
return 1;
}
复杂度分析
- 时间复杂度：对于一个整数不断取模运算，直到整数为0，时间复杂度为$O(n)$
- 空间复杂度：空间复杂度为$O(1)$
京公网安备 11010502036488号