神秘数

题目描述 倘若一个数它的立方的后三位全是1，我们称此类数为神秘数。现在我们想知道第K个这样的数是多少，相信你能解决。 输入 输入一个正整数K，直到文件结束,K的位数最多100位。 输出 输出第K个数，占一行 样例输入 1 样例输出 471

答案

这个其实算法很简单的，结果就是：(K-1)*1000＋471。 只需要用字符串实现大整数的加法。
通过枚举，我们可以知道在1-1000之内只有471是神秘数。下面我们来证明第K个神秘数就是 (K-1)*1000+471。

首先证明任何一个神秘数必然的末尾三位数都是471.
设神秘数的末尾三位数是abc， 那么任意一个神秘数n可以表示为： 1000*m + abc (其中m>=0)
下面的%为求模运算，n%1000表示n除以1000的余数
则

   (n^3)%1000 = ((1000*m + abc) ^3)%1000
              = (1000*(1000*m+abc)^2 + abc*(1000*m+abc))%1000
              = (1000*m*(1000*m+abc)^2 %1000 + abc*(1000*m+abc)^2%1000)%1000

而 1000*m*(1000*m+abc)^2 %1000 的结果为0
所以有

       (n^3)%1000 = (0 + abc*(1000*m + abc)^2%1000)%1000
                  = (abc*(1000*m + abc)%1000)%1000
                  = (abc*(1000*m + abc)^2)%1000
                  = (abc*1000*m*(1000*m+abc) + abc*abc*(1000*m+abc)) %1000
                  = (abc*1000*m*(1000*m+abc)%1000 + abc*abc*(1000*m + abc)%1000) % 1000
                  = (0 + abc*abc*(1000*m+abc)%1000)%1000
                  = (abc^2*(1000*m+abc))%1000
                  = (abc^2*1000*m + abc^3) %1000
                  = (abc^2*1000*m % 1000 + abc^3%1000) %1000
                  = (0  + abc^3 % 1000) %1000
                  = abc^3 % 1000 = 111

所以，n的末尾三位数也是一个神秘数， 而在1-1000以内只有471是神秘数，故abc=471， 所以任何神秘数n都可以写成 1000*m + 471的形式，当m=0时是471， m=1时外1471， 依次内推 2471, 3471,4471.... 我们不难发现第K个神秘书就是(k-1)*1000 + 471.

弄清楚了这一点，下程序就很简单了，（下面的程序是从控制台输入）：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char k[110];
    int i=0, len;
    scanf("%s", k);

    for(i=0; k[i]!='\0'; i++);

    len = i;

    if(i==1 && k[0] == '1') //处理K=1的特殊情况。
    {
        printf("471\n");
        return 0;
    }

    //从最低位开始计算K-1

    for(i=len-1; i>=0; i--) {
        if(k[i] == '0') { //当前位是0，需要从高位借1，算法继续循环
            k[i] = '9';
        }
        else {  //当前位已经够减1,这个1可能是借给低位的也可能是末位的时候减1
            k[i] -= 1;
            break;  //跳出循环，K-1已经计算完毕。
        }
    }

    // 将471之间追加到 K-1后面，就得到了(k-1)*1000+471.
    k[len] = '4';
    k[len+1] = '7';
    k[len+2] = '1';
    k[len+3] = '\0';

    //打印结果
    for(i=0; k[i]=='0'; i++);  //跳过最前面的0.

    for(;k[i]!='\0'; i++) {
        printf("%c", k[i]);
    }
    printf("\n");

    return 0;
}