2288: 【基础】小X转进制

flowchart 箭头图标 勿删

2288: 【基础】小X转进制

时间限制: 1 Sec 内存限制: 256 MB

提交: 1316 解决: 576

[提交] [状态] [讨论版] [命题人:ghost79]

题目描述

小X喜欢研究进制转换。

 在了解了进制转换的一般流程后，小X突然想起了以前学过的回文数（正着读倒着读都一样的数），于是开始思考一个奇怪的问题：1到N 中有多少个整数的平方在M进制下是回文数呢？

小X随手列了几个：

   2的平方4，10进制表示为4，是回文数；

   3的平方9，2进制表示为 1001，是回文数；

   9046的平方81830116，16进制表示为4E0A0E4，是回文数。

 小X觉得要全列出来太难了，希望你帮帮他。

输入

第一行包含用一个空格隔开的两个整数N,M。

输出

第一行包含一个整数，表示满足要求的整数个数。

样例输入

2 10

样例输出

2

提示

数据范围

   对于30%的数据，M=10。

   对于另外30%的数据，M=2。

   对于 100%的数据，1≤N≤10000，2≤M≤16。

来源/分类

常州市2015“信息与未来”夏令营选拔赛

---

题解如下

#include<stdio.h>

#include<string.h>

int main()

{

    int m,b;

    scanf("%d%d",&m,&b);

    int sum=0;

    for(int o=1;o<=m;o++)

    {

        int n=o*o;

        char ar[20];

        for(int i=0;i<20;i++)

        {

            if(i<=9)

                ar[i]=i+'0';

            else

                ar[i]=i+55;

        }

        char result[999];

        int count_zero=0;

        int position=0;

        if(n==0)

        {

            //printf("0");

            result[position++]='0';

        }

        else

        {

            for(int i=0; ;i++)

            {

                if(n%b==0)

                {

                    count_zero++;

                    n/=b;

                }

                else

                    break;

            }

            for(int j=0; ;j++)

            {

                if(n/b!=0)

                {

                    //printf("%c\n",ar[n%b]);

                    result[position++]=ar[n%b];

                    n/=b;

                    //printf("@\n");

                }

                else

                {

                    //printf("#\n");

                    // printf("%c\n",ar[n]);

                    result[position++]=ar[n];

                    break;

                }

            }

            for(int i=0;i<count_zero;i++)

                //printf("0");

                result[position++]='0';

        }

        int LEN_re=(int)strlen(result);

        //printf("%d\n\n",LEN_re);

        int flag=1;

        for(int i=0;i<LEN_re/2;i++)

        {

            if(result[i]!=result[LEN_re-1-i])

                flag=0;

        }

        if(flag==1)

            sum++;

    }

    printf("%d",sum);

    return 0;

}