算法15---数论4---自守数

如果一个正整数的平方的末尾几位数等于这个数本身，那么这个数便称为自守数。

自守数有如下的一些性质

（1）以自守数为后几位的两数相乘，结果的后几位仍是自守数；

（2） n+1位的自守数出自n为的自守数。

（3）两个n位子守数的和等于10的n次方加1.

我们给出两种自守数的算法

  1 /*
  2     题目：自守数
  3     author taoliu——alex  2016.10
  4 
  5     主要实现：
  6     判断自守数；
  7 
  8 */
  9 
 10 
 11 #include <stdio.h>
 12 #include <math.h>
 13 
 14 int digit(long n)
 15 {
 16     int count=0;//记录n的位数,这种方法比我在水仙花数中之前用到的有点不同。
 17 
 18     while(n>0)
 19     {
 20         n=n-(long)pow(10,count);
 21 
 22         count++;
 23     }
 24     return count-1;
 25 }
 26 
 27 /*
 28 这是一种最为直观的方法求自手术，但是这样也会存在一定的问题，就是当n比较大的时候
 29 要求n的平方，结果就会非常的大,印象计算速度，另一方面也容易造成数据范围溢出。
 30 */
 31 int zishoushu1(long n)
 32 {
 33     int digit_capacity=digit(n);//求n的位数
 34     long temp=(n*n)%(long)(pow(10,digit_capacity));
 35     if (temp==n)
 36     {
 37         return 1;
 38     }
 39     else
 40         return 0;
 41 }
 42 
 43 /*
 44 
 45 在这里我们采用另一种方法来求，我们只需要知道后面的即为，但是在乘法计算中
 46 后面的位数并不是需要与所有的被成熟想成才能知道的。
 47 下面我们以625的平方为例来说明。
 48         6 2 5
 49     X   6 2 5
 50     ——————————
 51       3 1 2 5
 52     1 2 5 0
 53   3 7 5 0
 54   _____________
 55   3 9 0 6 2 5
 56 
 57   对于自守数625来说，我们只需要知道后面的3位数就行了，而不必计算整个平方的
 58   结果，在上面计算的过程中可知道并不是它的每一位都会对乘积的后三位产生影响。
 59   规律如下：
 60       对于个位数与被乘数相乘的积中，用被乘数的后3位625与乘数的个位5相乘；
 61       对于十位数与被乘数相乘的积中，用被乘数的后2位25与乘数的十位20相乘；
 62       对于百位数与被乘数相乘的积中，用被乘数的后1位5与乘数的百位600相乘；
 63   对于以上各位相乘的积累加，再取最后三位即可。
 64   实现如下：
 65 */
 66 
 67 //用一个函数得到num的后n位,如124后2位24；
 68 long cut_num(long num,int n)
 69 {
 70     int c_t=digit(num);
 71 
 72     if (n>c_t)
 73     {
 74         printf("worry n !
");
 75     }
 76     long m=num;//用来保存后n位
 77     m=m%(long)(pow(10,n));
 78     return m;
 79 }
 80 
 81  int zishoushu2(long num)
 82  {
 83      long sum=0;
 84      int i=1;
 85      int count = digit(num);
 86      //printf("the count is %d
",count);
 87      int count2=count;
 88      while(count>0)
 89      {
 90          sum=sum+cut_num(num,count)*(cut_num(num,i)-cut_num(num,i-1));
 91          count--;
 92          i++;
 93      }
 94      long ans=cut_num(sum,count2);
 95      printf("the ans is %ld
",ans );
 96      if(ans==num)
 97      {
 98          return 1;
 99      }
100      else
101          return 0;
102 
103 
104  }
105 
106 
107 int main()
108 {
109     printf("please input the  number you want to judge! 
");
110     long n;
111     scanf("%ld",&n);
112     int judge=zishoushu2(n);
113     if (judge==1)
114     {
115         printf("the number %ld is zishou number 
",n );
116     }
117     else
118         printf("the number %ld is not zishou number 
",n );
119     return 0;
120 }

 1 /*
 2     题目：保存数字的后n位
 3     author taoliu——alex  2016.10
 4 
 5     疑惑点：
 6     为什么后两位就出错，此外其他位都没有问题
 7     比如
 8     625  后两位的结果显示31，但是其他为都正常，我找不出原因。
 9     后来换了其他的编辑器，显示的没问题，看来我这个编辑器有点问题啊
10 
11 
12 
13 */
14 #include <stdio.h>
15 #include <math.h>
16 
17 int digit(long n)
18 {
19     int count=0;//记录n的位数,这种方法比我在水仙花数中之前用到的有点不同。
20 
21     while(n>0)
22     {
23         n=n-(long)pow(10,count);
24 
25         count++;
26     }
27     return count-1;
28 }
29 
30 long cut_num(long num,int n)
31 {
32     int c_t=digit(num);
33 
34     if (n>c_t)
35     {
36         printf("worry n !
");
37     }
38     long m=num;//用来保存后n位
39     m=m%(long)(pow(10,n));
40     return m;
41 }
42 
43 
44 int main()
45 {
46     long ans=cut_num(625,2);
47     printf("%ld
",ans);
48     return 0;
49 }

换了编译器后的结果显示