自守?cái)?shù)是指一個(gè)數(shù)的平方的尾數(shù)等于該數(shù)自身的自然數(shù)。例如：

52 = 25 252 = 625 762 = 5776 93762 = 87909376

求100000以內(nèi)的自守?cái)?shù)。
問題分析
根據(jù)自守?cái)?shù)的定義，求解本題的關(guān)鍵是知道當(dāng)前所求自然數(shù)的位數(shù)，以及該數(shù)平方的尾數(shù)與被乘數(shù)、乘數(shù)之間的關(guān)系。
算法設(shè)計(jì)
若采用“求出一個(gè)數(shù)的平方后再截取最后相應(yīng)位數(shù)”的方法顯然是不可取的，因?yàn)橛?jì)算機(jī)無(wú)法表示過大的整數(shù)。

分析手工方式下整數(shù)平方（乘法）的計(jì)算過程，以376為例：




本問題所關(guān)心的是積的最后三位。分析產(chǎn)生積的后三位的過程可以看出，在每一次的部分積中，并不是它的每一位都會(huì)對(duì)積的后三位產(chǎn)生影響�？偨Y(jié)規(guī)律可以得到：在三位數(shù)乘法中，對(duì)積的后三位產(chǎn)生影響的部分積分別為：

第一個(gè)部分積中：被乘數(shù)最后三位×乘數(shù)的倒數(shù)第一位。
第二個(gè)部分積中：被乘數(shù)最后二位×乘數(shù)的倒數(shù)第二位。
第三個(gè)部分積中：被乘數(shù)最后一位×乘數(shù)的倒數(shù)第三位。

將以上的部分積的后三位求和后，截取后三位就是三位數(shù)乘積的后三位，這樣的規(guī)律可以推廣到同樣問題的不同位數(shù)乘積中。
分離給定數(shù)中的最后幾位
從一個(gè)兩位數(shù)（存在變量n中）開始分析，分離最低位個(gè)位n%10；對(duì)于三位數(shù)n，分離最后兩位n%100；對(duì)于四位數(shù)n，分離最后三位n%1000；...，由此可見，若分離出最后x位，只需要用原數(shù)對(duì) 10x 求余。

從第3部分所舉例子可以看出，對(duì)于第二個(gè)部分積“2632”來說其實(shí)應(yīng)是“26320”， 因?yàn)閷?duì)于乘數(shù)中的倒數(shù)第二位“7”來說，因其在十位，對(duì)應(yīng)的權(quán)值為10，第二個(gè)部分積實(shí)質(zhì)上為：376X70=26320。故求部分積的程序段為：


int main ()
{
    //...
    while(k>0)
    {
        mul=( mul + ( number%(k*10) )*( number%b - nxuober%(b/10) ) )%a;
        /* (部分積+截取被乘數(shù)的后N位*截取乘數(shù)的第M位），%a再截取部分積*/
        k /= 10;  /*k為截取被乘數(shù)時(shí)的系數(shù)*/
        b *= 10;
    }
    //...
    return 0;
}
對(duì)于整個(gè)循環(huán)來說，變量k是由number的位數(shù)確定截取數(shù)字進(jìn)行乘法時(shí)的系數(shù)。第1次執(zhí)行循環(huán)體時(shí)，被乘數(shù)的所有位數(shù)都影響到平方的尾數(shù)，因此第1個(gè)部分積=被乘數(shù)*乘數(shù)的最后一位，將部分積累加到變量mul上，再對(duì)a取余截取相應(yīng)的尾數(shù)位數(shù)；第2次執(zhí)行循環(huán)體，影響平方尾數(shù)的是被乘數(shù)中除了最高位之外的數(shù)（所以k先除以10再參加運(yùn)算），第2個(gè)部分積=被乘數(shù)*乘數(shù)的倒數(shù)第二位，( number%b - number%(b/l0) )用來求乘數(shù)中影響平方尾數(shù)的對(duì)應(yīng)位上的數(shù)；第3次、第4次執(zhí)行循環(huán)體的過程同上。

程序流程圖：



下面是完整的代碼：

#include<stdio.h>
int main()
{
    long mul, number, k, a, b;
    printf("It exists following automorphic nmbers small than 100000:\n");
    for( number=0; number<100000; number++ )
    {
        for( mul=number, k=1; (mul/=10)>0; k*=10 );
        /*由number的位數(shù)確定截取數(shù)字進(jìn)行乘法時(shí)的系數(shù)k*/
        a = k * 10;  /*a為截取部分積時(shí)的系數(shù)*/
        mul = 0;  /*積的最后n位*/
        b = 10;  /*b為截取乘數(shù)相應(yīng)位時(shí)的系數(shù)*/
        while(k>0)
        {
            mul=( mul + ( number%(k*10) )*( number%b - number%(b/10) ) )%a;
            /*(部分積+截取被乘數(shù)的后N位*截取乘數(shù)的第M位)，%a再截取部分積*/
            k /= 10;  /*k為截取被乘數(shù)時(shí)的系數(shù)*/
            b *= 10;
        }
        if(number == mul)  /*判定若為自守?cái)?shù)則輸出*/
            printf("%ld   ", number);
    }
    printf("\n");
    
    return 0;
}</stdio.h>
運(yùn)行結(jié)果：
It exists following automorphic nmbers small than 100000:
0 1 5 6 25 76 376 625 9376 90625