编程题|每日一题（尾数相等）算法|c语言

题目描述

对于任意一个大于1的整数K，一定存放两个自然数M,N(其中M

KM>=1000

KN>=1000

KM和KN末尾三位数相等
现在给定一个任意正整数K,求出满足条件的最小M+N的值

其中K的位数<=10

思路在这道题中，K的位数小于10，这样KM就会是一个很大的数字，大数在C语言中无法储存
不过万幸的是，我们只需要计算这个数字的后三位即可
所以这里的处理方法是：只需要计算后三位，对计算结果没有影响
取出后三位的方法：k%=1000
而这道题我们进行乘方的数是同一位数字，所以我们可以采取试乘的方法，从1一直乘下去，一直跟踪后三位数，直到重复出现为止
怎么存储呢？
我们可以采用数组的方式
【编程题|每日一题（尾数相等）】定义一个下标从1-1000的数组，首先设置为0，只要后三位数第一次出现，则把这三位数对应的数组下标的值设置为出现这次下标的指数，也就是M继续，直到某一次的下标值不为0
代码实现

int main() { int k = 0; scanf("%d", &k); int count[1000] = { 0 }; int flag = 0; int m = 0; int pow = 1; //用于储存后三位数 //初始化阶段*************************** if (k >= 1000) {k %= 1000; flag = 1; } //flag用于标记真正的k值是否已经大于1000了 while (1) {m++; pow *= k; if (flag || pow >= 1000) {pow %= 1000; if (count[pow] == 0) count[pow] = m; //这里将这次后三位数出现的指数储存在这三位数的数组下标中 else break; //重复出现则结束程序，把此次的m作为n值 flag = 1; } } printf("%d,%d", count[pow], m); //m,n格式的输出 return 0; }