首页 > 试题广场 >

自守数

[编程题]自守数

热度指数：158524 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 自守数是指这样一个自然数 $x$ ，其平方的尾数等于自身。更具体的说，即 $x^2$ 的末尾若干位恰好等于 $x$ ，例如：
$\hspace{23pt}\bullet\,$ $25^2=625$ ， $625$ 的末尾两位恰好是 $25$ ；
$\hspace{23pt}\bullet\,$ $76^2=5776$ ， $5776$ 的末尾两位恰好是 $76$ ；
$\hspace{23pt}\bullet\,$ $9\,376^2=87\,909\,376$ ， $87\,909\,376$ 的末尾四位恰好是 $9\,376$ 。
$\hspace{15pt}$ 现在，对于给定的 $n$ ，请统计 $0$ 到 $n$ 之间的自守数个数。

输入描述:

输入一个整数  代表自守数的范围。

输出描述:

输出一个整数，代表  到  之间的自守数个数。

示例1

输入

输出

说明

在这个样例中， 是自守数。

算法知识视频讲解

Python

东方那条龙

while 1:
    try:
        n = int(input())
        res = 0
        for i in range(n+1):
            temp = str(i*i)
            l = len(str(i))
            if temp[-l:] == str(i):
                res += 1
        print(res)
    except:
          break

发表于 2020-02-01 16:41:02 回复(2)

Java

米斯特rollin

将 i 和 i * i 转为字符串进行比较，查看i与i*i的末尾是否相同即可。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int count = 0;
            for (int i = 0; i <= n; i++) {
                String str = String.valueOf(i * i);
                String index = String.valueOf(i);
                // 比较 i的值是否与i*i的最后相同
                if (index.equals(str.substring(str.length() - index.length()))) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2022-05-05 07:43:17 回复(0)

Java

Robin丶Z

//深度优先遍历，从1，5，6开始，在他们是自守数的情况下在头部尝试添加1到9。
//若添加后不构成自守数，则放弃往下dfs，否则，count++，继续向下深搜。
//时间复杂度从O(N)降低到O(log(N))...不晓得这个算对没..
import java.util.*;
public class Main {
    public static int count = 1;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            int[] nums = new int[]{1,5,6};
            for(int i = 0; i < 3; i++) {
                int cur = nums[i];
                dfs(cur, n);
            }
            System.out.println(count);
            count = 1;
        }
    }
    
    public static void dfs(int cur, int n) {
        if(cur > n)
            return;
        if(check(cur)) {
            count++;
            for(int j = 1; j < 10; j++) {
                String tmp = String.valueOf(cur);
                tmp =j + tmp;
                int tmpCur = Integer.parseInt(tmp);
                dfs(tmpCur, n);
            }
        }
    }
    
    public static boolean check(int i) {
        String a = String.valueOf(i);
        int c = i*i;
        String b = String.valueOf(c);
        int cura = a.length()-1;
        int curb = b.length()-1;
        while(cura >= 0) {
            if(a.charAt(cura) != b.charAt(curb))
                return false;
            cura--;
            curb--;
        }
        return true;
    }
}

发表于 2020-07-28 16:46:42 回复(1)

JavaScript

猥琐的水完熊

while( n = readline()){
            var res = [];
    for(var num = 0 ; num <= +n ; num ++){
        var len = (num + '').length;
        var str = (num + '');
        var all = 0;
        var istrue = true;
        for(var i = 0 ; i < len ; i ++){
            for(var j = 0 ; j <= i ; j ++){
                all += str[len-1-j] * str[len-1-(i-j)] * Math.pow(10, i);
            }
            if((all + '').slice(-i-1) !== str.slice(-i-1)){
                istrue = false;
                break;
            }
        }
        if(istrue) {
            res.push(num);
        }
    }
    console.log(res.length);
}

害怕暴力求解会产生问题，所以想了想办法先把乘法表达式分解，从后向前一位一位的乘，比如9376，先计算最后一个数，应该为6*6取后一位，为6，在计算最后两位6*6+6*7*10+7*6*10=876，也满足，再计算后三位，876 + 3*6*10^2 + 7*7*10^2 + 6*3*10^2 = 9376, 也满足，再计算最后四位，9376 + 9*6*10^3 + 3*7*10^3 + 7*3*10^3 + 6*9*10^3 = 159376,至此已经计算了后四位没必要再计算了，而且满足条件，则成立。

发表于 2020-06-09 14:59:54 回复(1)

C/C++

danqiuBear

//自己写个判断函数，也很简单的
#include<iostream>
using namespace std;
bool isZiShouShu(int num){//判断是否为自守数
    long long squrtNum = num*num;
    while (squrtNum && num){
        if (squrtNum % 10 != num % 10){
            return false;
        }
        else{
            squrtNum /= 10;
            num /= 10;
        }
    }
    return true;
}
int main(){
    int n;
    while (cin >> n){
        int cnt = 0;
        for (int i = 0; i <= n; i++){
            if (isZiShouShu(i))cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

发表于 2019-07-21 21:30:58 回复(1)

C/C++

Hmmmmmmm_y

#include  <bits/stdc++.h>
using namespace std;
bool automor(int x)
{
    int y=x*x;
    while(x)
    {
        if(x%10==y%10)
        {
            x/=10;
            y/=10;
        }
        else break;
    }
    if(x==0) return true;
    else return  false;

}
int main()
{
    int n;
    while(cin>>n)
    {
         bool res;
         int cnt=0;
         for(int i=0;i<n;i++)
         {
             if(automor(i)) cnt++;
         }
        cout<<cnt<<endl;
    }

    system("pause");
    return 0;
}

编辑于 2018-08-05 11:43:39 回复(1)

Python

fhqplzj

while True:
    try:
        print len(filter(lambda x: str(x ** 2).endswith(str(x)), range(input())))
    except EOFError:
        break

编辑于 2017-03-08 22:23:49 回复(1)

贱贱的梦想

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int num = sc.nextInt();
            int count = 0;
            while(num >= 0){
            	long num_square = num * num;
            	char[] c1 = String.valueOf(num_square).toCharArray();
            	char[] c2 = String.valueOf(num).toCharArray();
            	int c1_length = c1.length;
            	int c2_length = c2.length;
            	int i;
            	for(i = 1; i <= c2_length; i++){
            		if(c1[c1_length - i] != c2[c2_length - i])
            			break;
            	}
            	if(i == c2_length + 1)
            		count++;
            	num--;
            }
            System.out.println(count);
        }
        sc.close();
    }
}

发表于 2016-08-11 15:52:23 回复(0)

尘烟

我说怎么看不懂题目，原来 252=625，252最后那个2是平方的意思，***

发表于 2016-07-28 10:13:21 回复(2)

Python 3

来个offer叭！

n = int(input())
num = 0
for i in range(n+1):
    x = i * i
    length = len(str(i))
    # 用字符串比较
    if str(i) == str(x)[-length:]:
        num += 1
print(num)

发表于 2022-07-30 19:22:59 回复(0)

C++

已注销

for(int i = 0; i <= n; ++i)
        {
            int div = 10;
            if(i < 10)div = 10;
            else if(i < 100)div = 100;
            else if(i < 1000)div = 1000;
            else if (i < 10000)div = 10000;
            else div = 100000;
            if(((i*i - i)%(div)) == 0)++num;
        }
        cout << num;

发表于 2022-07-17 13:26:02 回复(0)

Python3

正在学习的小李

while True:
    try:
        s0 = int(input())
        ss = [x for x in range(s0+1) if str(x) == str(x**2)[-len(str(x)):]]
        print(len(ss))
    except:
        break

发表于 2022-05-31 13:45:20 回复(0)

Python 3

Frankzj

## 额，我把字符串倒排，然后用string.find()看是不是=0
while True:
    try:
        n = int(input())
        res = 0
        for i in range(0,n+1):
            sq = i ** 2
            i = str(i)[::-1]
            sq = str(sq)[::-1]
            if sq.find(i) == 0:
                res += 1
        print(res)
    except:
        break

发表于 2022-01-22 22:48:09 回复(0)

Java

奥因克

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int count = 0;
            for(int i = 0 ;i <= n;i++){
                if(isZiShouShu(i)){
                    count ++;
                }
            }
            System.out.println(count);
        }
    }
    public static boolean isZiShouShu(int num){
        int result = num * num;
        String numStr = ""+num;
        String resultStr = ""+result;
        int index = resultStr.length()-numStr.length();
        if(resultStr.substring(index).equals(numStr)){
            return true;
        }else{
            return false;
        }
    }
}

endsWith方法:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int count = 0;
            for(int i = 0 ;i <= n;i++){
                int num = i*i;
                if(String.valueOf(num).endsWith(String.valueOf(i))){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2021-12-01 16:23:24 回复(0)

Java

牛客150518786号

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            System.out.println(CalcAutomorphicNumbers(n));
        }
        br.close();
    }

    private static int CalcAutomorphicNumbers(int n) {
        int count = 0;
        for (int i = 0; i <= (n); i++) {
            String str1 = String.valueOf(i);
            String str2 = String.valueOf(i * i);
            if (str2.endsWith(str1)) {
                count++;
            }
        }
        return count;
    }
}

发表于 2021-09-28 10:57:35 回复(0)

肥嘟嘟就是肥嘟嘟

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            System.out.println(self_num(n));
        }
    }
    
    public static int self_num(int n){
        int count = 0;
        for(int i = 0; i <= n; i++){
            if(is_self_num(i)) count++;
        }
        return count;
    }
    
    public static boolean is_self_num(int i){
        int power_two = i*i;
        if(power_two == 1 || power_two == 0) return true;
        int devide = 10;
        while(power_two/devide != 0){
            if(power_two % devide == i) return true;
            else devide *= 10;
        }
        return false;
    }
}

发表于 2021-09-15 15:17:34 回复(0)

Python 3

牛客452788428号

为啥题目说n以内却包括n呢

发表于 2021-09-04 19:54:13 回复(0)

Java

80后大叔

系统方法endsWith搞定

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int CalcAutomorphicNumbers( int n)
    {
        String a = String.valueOf(n*n);
        String b = String.valueOf(n);
        if(a.endsWith(b) == true) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int num = 0;
            for(int i = 0; i <= a; i++) {
                if(CalcAutomorphicNumbers(i) == 1) {
                    num++;
                }
            }
            System.out.println(num);
        }
    }
}

发表于 2021-09-01 11:04:30 回复(0)

Java

GeraltoffRivia

/**
 * 
 */


import java.util.Scanner;

/**
 * @author April Chou
 *
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
			while(sc.hasNext()) {
			System.out.println(countAutomorphicNumbers(sc.nextInt()));
		}
		
		sc.close();
	}
	
	public static int countAutomorphicNumbers(int input) {
		int flag = 0;
		for(int i=0; i<=input; i++) {
			long result = i * i;
			String numI = i + "";
			String number = result + "";

			if(number.endsWith(numI)) {
				flag ++;
			}
		}
		return flag;
		
	}

}

直接调用String endsWith就搞定了啊

发表于 2021-08-05 18:00:37 回复(1)

上大-黄志栋

while True:
    try:
        n, cnt = int(input()), 0
        for i in range(n+1):
            x ,y = str(i*i),str(i)
            if x[-len(y):] == y:
                cnt += 1
        print(cnt)
    except:
        break

发表于 2020-07-17 17:15:33 回复(0)