ACM复习（5）1076 K尾相等数

本文主要是介绍ACM复习（5）1076 K尾相等数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
从键盘输入一个自然数K（99999999>K>1），若存在自然数M和N（M>N），使得K的M次方和K的N次方均大于或等于1000，
且它们的未尾三位数相等，则称M和N是一对“K尾相等数”。请编程序，输出K尾相等数中M+N最小值。

输入样例
2

输出样例
120

---

解题思路

因为1 < K < 99999999 所以K的次方可能是超范围的数，但题目只要求次方中的末尾三位相等。
可以得到下列运算过程：
在 K * K * K * K * K…的过程中每做完一个运算（即K * K）将结果 % 1000，保存余数并且用
余数继续K的次方运算。因为对1000取余数结果必定小于1000，所以余数乘上K也不会超范围，
并且对1000取余数的结果数最多只有1000个（0 - 999），所以只需1000次运算后必定出现
重复，即 K的M次方%1000 == K的N次方%1000

将1001个余数保存后遍历数组即可得到最小M+N

#include<stdio.h>
int main()
{int num[1004][2], k, j, count = 1, i = 0, min = 10000;scanf("%d", &k);j = k;// K < 1000时先将K运算到大于1000// count为当前K的次方数while(j < 1000){j *= k;count ++;}// 循环1001次，必定出现余数重复while(i < 1002){num[i][0] = j % 1000;num[i][1] = count ++;j = num[i][0] * k;i ++;}for(int w = 0; w < i - 1; w ++){for(int e = w + 1; e < i; e ++){if(num[w][0] == num[e][0])min = min < num[w][1] + num[e][1] ? min : num[w][1] + num[e][1];}}printf("%d\n", min);return 0;
}   

---

这篇关于ACM复习（5）1076 K尾相等数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---