【ACM】K尾相等数

问题描述：
从键盘输入一个自然数K（K>1），若存在自然数M和N（M>N），使得K^M 和K^N均大于或等于1000，且它们的末尾三位数相等，则称M和N是一对"K尾相等数"。请编写程序，输出M+N最小的K尾相等数。

样例：

输入	输出
2	120

问题分析：末尾三位数只有1000个，从1到无穷大增大幂次时，肯定会出现同样的末尾三位数，比如n=10时（`n^M`大于1000时才有末尾三位数），

幂次M	1	2	3	4	5
n^M	10	100	1000	10000	100000
末尾三位数	无	无	0	0	0

所以当幂次为3时出现了第一个三位数，当幂次为4时出现了第二个三位数，N = 3，M = 4，且M+N最小。所以只要最先**两次**==出现在同一个三位数框里的两个幂次就是我们所求的M和N==。

代码如下：

#include <iostream>
using namespace std;

int main(){
	int n;
	while(cin>>n) {
		int arr[1000]={
			0
		};
		bool b = false;
		if(n>=1000) {
			b = true;
			n=n%1000;
		}
		int c = 0;
		int k = 1;
		while(true){
			c+=1;
			k*=n;
			if(k>=1000 || b == true) {
				k=k%1000;
				if(arr[k]==0) {
					arr[k]= c;
				} else {
					break;
				}
			}
				
		}
		cout<<(c+arr[k])<<endl;
	}
	return 0;
}