首页 > 代码库 > K尾相等数
K尾相等数
问题
对于一个自然数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。
注意点
- K是一个自然数，可能大于1000，可能小于1000。在累乘时，真正对三位尾数有贡献的是后三位，即K % 1000，因此要对K进行预处理。
- 如果K小于1000，前几次幂很可能也小于1000，此时即便出现了重复的尾数，也不能采用。
- 确定尾数是否重复，要对之前在幂大于1000时出现过该尾数的下标进行记录。因为尾数只有1000个，因此开一个长度至少1000的数组记录即可。
代码实现
#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)。
Ref
郭嵩山老师算法课程
K尾相等数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。