Question

C++的求自守数的问题

#include <iostream>
using namespace std;
int main()
{
double m,n;
cout<<"请输入两个2~200000之间的数"<<endl;
cin>>m>>n;
int b;
int c=1;
int d=0;
while (m<=n)
{
b=m*m;
while (c<=m)
c=c*10;
if (b%c==m)
{
d++;
cout<<m<<" ";
if(d%5==0)
cout<<endl;
}
m++;
}
cout<<endl;
system ("pause");
return 0;
}

为什么他只能求道10000之后的就求不了了，怎么改才可以输出后面的，最好不要太大的修改，谢谢！

Answer 1

b=m*m
b是int，范围2^-31到2^31，当m>2^16=65536时，b会溢出，无法正确求解
而9376下一个自守数是90625，肯定是求不出来的

解决方案：
如果不想写大整数乘法除法，或者调用非标准C++中的64位整型，那么可以借助数学手段简化问题

原题为求m，使m*m与m关于10^k同余，其中k是m的位数
那么就有m*m-m可以被10^k整除，
即m*(m-1)被2^k*5^k整除，
而m与(m-1)互质，则可以知道(2^k 整除 m && 5^k 整除 m-1) || (2^k 整除 m-1 && 5^k 整除 m)

代码：
#include <iostream>
using namespace std;
int main()
{
int m,n;
cout<<"请输入两个2~200000之间的数"<<endl;
cin>>m>>n;
int c=1;
int e=1,f=1;//修改处
int d=0;
while (m<=n)
{

while (c<=m)//修改处c=10^k,e=2^k,f=5^k
{
c=c*10;
e=e*2;
f=f*5;
}
if ((m%e==0 && (m-1)%f==0)||(m%f==0 && (m-1)%e==0))//修改处
{
d++;
cout<<m<<" ";
if(d%5==0)
cout<<endl;
}
m++;
}
cout<<endl;
system ("pause");
return 0;
}

Answer 2

我没学过自守数，但我搜索到有关它的代码，其中有c++的
http://baike.baidu.com/view/604315.htm

Answer 3

那就是只有这几个是自守数了
用__int64吧

追问

恩，后来知道这种可以了，但想用数学手段简化。。。