对于一个自然数K（K>1），若存在自然数M和N（M>N），使得KM和KN均大于或等于1,000，且它们的末尾三位数相等，则称M和N是一对“K尾相等数”。
求M+N值最小的K尾相等数。
一个数的幂随着指数的增长有无穷个，但是末尾的3位数最多有1000个（000-999），因此这些幂的位数一定会重复。在确定了第a次幂的尾数之后，第a+1的尾数也可以确定。因此当出现了第一个重复尾数的尾数时，我们就可以找的最小的M和N。
#include <iostream> using namespace std; int tail[1001]; int main() { memset(tail, 0, 1001); int K; cin >> K; int result = 1; int i = 0; bool moreThanEqual_1000 = false; int power = 0; // 预处理K，因为只有后三位有用 if (K >= 1000) { K = K % 1000; moreThanEqual_1000 = true; } while (true) { power++; result = result * K; if (result >= 1000 || moreThanEqual_1000) { result %= 1000; moreThanEqual_1000 = true; if (tail[result] == 0) { tail[result] = power; } else { break; } } } cout << tail[result] << " " << power << endl; return 0; }
可以看到，假设M<N，则时间复杂度为O(N)。
郭嵩山老师算法课程
原文：http://www.cnblogs.com/HolyChen/p/5971316.html