Chinaunix首页 | 论坛 | 博客
  • 博客访问: 558617
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: C/C++

2011-11-28 10:51:02

题目描述 倘若一个数它的立方的后三位全是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的余数

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

而 1000*m*(1000*m+abc)^2 %1000 的结果为0
所以有
  1.        (n^3)%1000 = (0 + abc*(1000*m + abc)^2%1000)%1000
  2.                   = (abc*(1000*m + abc)%1000)%1000
  3.                   = (abc*(1000*m + abc)^2)%1000
  4.                   = (abc*1000*m*(1000*m+abc) + abc*abc*(1000*m+abc)) %1000
  5.                   = (abc*1000*m*(1000*m+abc)%1000 + abc*abc*(1000*m + abc)%1000) % 1000
  6.                   = (0 + abc*abc*(1000*m+abc)%1000)%1000
  7.                   = (abc^2*(1000*m+abc))%1000
  8.                   = (abc^2*1000*m + abc^3) %1000
  9.                   = (abc^2*1000*m % 1000 + abc^3%1000) %1000
  10.                   = (0 + abc^3 % 1000) %1000
  11.                   = 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.

弄清楚了这一点,下程序就很简单了,(下面的程序是从控制台输入):

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

  3. int main()
  4. {
  5.     char k[110];
  6.     int i=0, len;
  7.     scanf("%s", k);

  8.     for(i=0; k[i]!='\0'; i++);
  9.     
  10.     len = i;
  11.     
  12.     if(i==1 && k[0] == '1') //处理K=1的特殊情况。
  13.     {
  14.         printf("471\n");
  15.         return 0;
  16.     }

  17.     //从最低位开始计算K-1
  18.     
  19.     for(i=len-1; i>=0; i--) {
  20.         if(k[i] == '0') { //当前位是0,需要从高位借1,算法继续循环
  21.             k[i] = '9';
  22.         }
  23.         else { //当前位已经够减1,这个1可能是借给低位的也可能是末位的时候减1
  24.             k[i] -= 1;
  25.             break; //跳出循环,K-1已经计算完毕。
  26.         }
  27.     }

  28.     // 将471之间追加到 K-1后面,就得到了(k-1)*1000+471.
  29.     k[len] = '4';
  30.     k[len+1] = '7';
  31.     k[len+2] = '1';
  32.     k[len+3] = '\0';
  33.     
  34.     //打印结果
  35.     for(i=0; k[i]=='0'; i++); //跳过最前面的0.
  36.     
  37.     for(;k[i]!='\0'; i++) {
  38.         printf("%c", k[i]);
  39.     }
  40.     printf("\n");

  41.     return 0;
  42. }

阅读(1744) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~