Problem1287--自守数

1287: 自守数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 67  Solved: 59
[Submit] [Status] [Web Board] [Creator:]

Description

如果一个自然数的平方数的尾部仍然为该自然数本身,则称其为自守数。
例如:

1x1=1
5 x 5 = 25
76 x 76 = 5776
625 x 625 = 390625

下面代码的目的是寻找出2千万以内的所有自守数。

注意,2千万的平方已经超出了整数表达的最大范围,所以该程序使用了一个巧妙的方案。
如果我们仔细观察乘法的计算过程,就会发现实际上对乘积的尾数有贡献的环节,从而不用真正计算出整个乘积。

输入:无

输出:2千万以内的所有自守数,每行一个

void zishou()
{
    int n;
    for(n=1; n<20 * 1000 * 1000; n++) {
        int n2 = n;
        int m = 0;
        for(;;) {
            if(n2==0) {
                printf("%d\n", n);
                break;
            }
            int k = n2 % 10; // 从末尾开始,取出乘数的每位数字
            m += k * n;   // 累计乘积
            if(_______________) break;
            m = m / 10;  // 舍去累计乘积的末位
            n2 = ____________;
        }
    }
}