题解 | #自守数#

自守数

http://www.nowcoder.com/practice/88ddd31618f04514ae3a689e83f3ab8e

自守数

描述

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

示例1

输入：5
2000
输出：3
8
说明：对于样例一，有0，1，5，这三个自守数

方法一：

思路分析

本题读完后的直接的思路是给定一个数，先求解出它的位数或者叫长度，然后将其平方的后面对应位数求出，比较两者的大小，如果两者值相等，那么这个数是自守数，这也是根据自守数的定义直接计算的

图解

$x$	$len(x)$	$x^2$	$x^2中后面len(x)位数$	$判断$
$25$	$2$	$625$	$最后2位=25$	$是$
$76$	$2$	$5776$	$最后2位=76$	$是$
$9376$	$4$	$87909376$	$最后2位=9376$	$是$
$11$	$2$	$121$	$最后2位=21$	$否$

核心代码

#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;
}