1890 - 【C语言训练】自守数问题

no input needed

0  1  5  6  25  76  376  625  9376  90625  109376  

Hint

	若采用“求出一个数的平方后再截取最后相应位数”的方法显然是不可取的，因为计算机无法表示过大的整数。 
分析手工方式下整数平方(乘法)的计算过程，以376为例： 

376 被乘数 

X 376 乘数 

---------- 

2256 第一个部分积=被乘数乘数的倒数第一位 

2632 第二个部分积=被乘数乘数的倒数第二位 

1128 第三个部分积=被乘数乘数的倒数第三位 

---------- 

141376 积 

本问题所关心的是积的最后三位。分析产生积的后三位的过程，可以看出，在每一次的部分积中，并不是它的每一位都会对积的后三位产生影响。总结规律可以得到：在三位数乘法中，对积的后三位产生影响的部分积分别为： 

第一个部分积中：被乘数最后三位乘数的倒数第一位 

第二个部分积中：被乘数最后二位乘数的倒数第二位 

第三个部分积中：被乘数最后一位乘数的倒数第三位 

将以上的部分积的后三位求和后截取后三位就是三位数乘积的后三位。这样的规律可以推广到同样问题的不同位数乘积。 

按照手工计算的过程可以设计算法编写程序。 

Solution C++

#include <iostream>

using namespace std;

int main()
{
    long long i,j=10;
    long long n;
    for(i=0;i<=200000;++i)
    {
        if(j<=i)
            j*=10;
        n=i*i;
        if(n%j==i)
           cout<<i<<"  ";
    }
    return 0;
}