WOJ-313-K尾数相等数

首先找到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;
}