gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2402--Palindrome Numbers
  1#include <cstdio>
  2#include <cmath>
  3const int MAX = 20;
  4
  5__int64 arr_bit[MAX]; //记录i个位有几个回文数
  6char strNum[50]; //保存结果
  7
  8void Cal()
  9{
 10    int i, j;
 11    __int64 t;
 12
 13    arr_bit[1] = 9;
 14
 15    for ( i = 2; i <= MAX; ++i )
 16    {
 17        arr_bit[i] = arr_bit[i - 1];
 18        t = 9;    
 19        for ( j = 0; j < (i >> 1) - 1; ++j )
 20                t *= 10;
 21        if ( i % 2 != 0 ){
 22            t *= 10;
 23        }
 24        arr_bit[i] += t;
 25    }
 26}
 27
 28void GetNum(const __int64& n)
 29{
 30    //对少于100的数直接输出
 31    if ( n <= 9 )
 32    {
 33        printf("%I64d\n", n);
 34    }
 35    else if ( n <= 18 )
 36    {
 37        printf("%I64d%I64d\n", (n - 9), (n - 9));
 38    }
 39    else {
 40        int i, pos, wh, t, k;
 41        __int64 del;
 42
 43        //找出当前数有多少个位
 44        for ( i = 3; i <= MAX; ++i )
 45        {
 46            if ( arr_bit[i] >= n )
 47            {
 48                pos = i;
 49                break;
 50            }
 51        }
 52
 53        //pos个位的第几个
 54        del = n - arr_bit[pos - 1] - 1;
 55
 56        wh = pos >> 1;
 57
 58        if ( pos % 2 == 0 ) {
 59            wh--;
 60        }
 61
 62        //确定每个位
 63        t = (int)pow(10, wh); 
 64        strNum[0] = strNum[pos - 1] = (int)(del / t) + 1 + '0';
 65        del = del % t;
 66        
 67        for ( i = wh - 1, k = 1; i >= 0; --i, ++k )
 68        {
 69            t = (int)pow(10, i);
 70            strNum[k] = strNum[pos - k - 1] = (int)(del / t) + '0';
 71            del = del % t;
 72        }
 73        
 74        strNum[pos] = '\0';
 75
 76        printf("%s\n", strNum);
 77
 78    }
 79
 80}
 81
 82int main()
 83{
 84    __int64 n;
 85
 86    Cal();
 87
 88    while ( true )
 89    {
 90        scanf("%I64d", &n);
 91
 92        if ( n == 0 )
 93            break;
 94
 95        GetNum(n);
 96    }
 97    return 0;
 98}
 99
100
101
102
posted on 2009-03-29 15:00 巫 阅读(217) 评论(0)  编辑 收藏 引用 所属分类: 数学

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理