首先找到pow(K,N)>1000的最小的N,然后求K的N次方,并保证后三位相同。
如何保证后三位相同,就是对1000取余数相同即可;我们利用一个a[1001]保存每个余数,其中下标表示对应的余数(对1000取余数,余数不可能大于1000),数组中存储的为对应的次方,只要找到一个不是-1的元素则表明寻找到了两个满足条件的元素。
注意使用:(x*y)%c=((x%c)*(y%c))%c
代码如下:
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main(){
int number,M,N;
int a[1001];//用来存储余数
cin>>number;
while(number!=0){
memset(a,-1, sizeof(a));//初始化为-1
M=N=0;
while(pow(number,N)<1000)
N++;
int temp=pow(number,N);
temp%=1000;
a[temp]=N;
for(M=N+1;;M++){
temp=((number%1000)*temp)%1000; //(x*y)%c=((x%c)*(y%c))%c
if(a[temp]==-1)
a[temp]=M;
else
break;
}
cout<<M+a[temp]<<endl;
cin>>number;
}
return 0;
}