题目

题目描述

输入一个基数B，现在要从1到300之间找出一些符合要求的数字N。如果N的平方转换成B进制数之后是一个回文串，那么N就符合要求。我们将N转换成B进制数输出，然后再将N的平方转换成B进制数输出来。注意，字母A, B分别表示数字10, 11，以此类推。

数据范围

1. 2 <= B <= 20
2. 1 <= N <= 300

样例输入

10

样例输出

1 1

2 4

3 9

11 121

22 484

26 676

101 10201

111 12321

121 14641

202 40804

212 44944

264 69696

解题思路

数据量比较小，所以我们直接枚举从1到300之间的每一个数字，然后将其平方转换成B进制数，判断是否是回文串。如果是则按照要求输出。

下面我用了两种方法来返回一个字符数组，一个用结构体包装，一个用指针来传递。

解题代码

/*

ID: yinzong2

PROG: palsquare

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 32;

char alph[20] = {'0', '1', '2', '3', '4',

                 '5', '6', '7', '8', '9',

                 'A', 'B', 'C', 'D', 'E',

                 'F', 'G', 'H', 'I', 'J'};

int base;

struct BBase {

    char str[MAXN];

};

BBase trans(int x) {

    BBase b;

    int len = 0;

    while(x) {

        b.str[len++] = alph[x%base];

        x /= base;

    }

    b.str[len] = '\0';

    return b;

}

bool judge(char s[]) {

    int len = strlen(s);

    for(int i = 0, j = len-1; i <= j; i++, j--) {

        if(s[i] != s[j]) {

            return false;

        }

    }

    return true;

}

int main() {

#ifdef MARK

    freopen("palsquare.in", "r", stdin);

    freopen("palsquare.out", "w", stdout);

#endif // MARK

    while(~scanf("%d", &base)) {

        for(int i = 1; i <= 300; i++) {

            BBase square = trans(i*i);

            if(judge(square.str)) {

                BBase iStr = trans(i);

                int len1 = strlen(iStr.str);

                for(int i = len1-1; i >= 0; i--) {

                    printf("%c", iStr.str[i]);

                }

                printf(" ");

                int len2 = strlen(square.str);

                for(int i = len2-1; i >= 0; i--) {

                    printf("%c", square.str[i]);

                }

                printf("\n");

            }

        }

    }

    return 0;

}

解题代码(Type 2)

/*

ID: yinzong2

PROG: palsquare

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 32;

char alph[20] = {'0', '1', '2', '3', '4',

                 '5', '6', '7', '8', '9',

                 'A', 'B', 'C', 'D', 'E',

                 'F', 'G', 'H', 'I', 'J'};

int base;

char *trans(int x) {

    char *b = new char[MAXN];

    int len = 0;

    while(x) {

        b[len++] = alph[x%base];

        x /= base;

    }

    b[len] = '\0';

    return b;

}

bool judge(char s[]) {

    int len = strlen(s);

    for(int i = 0, j = len-1; i <= j; i++, j--) {

        if(s[i] != s[j]) {

            return false;

        }

    }

    return true;

}

int main() {

#ifdef MARK

    freopen("palsquare.in", "r", stdin);

    freopen("palsquare.out", "w", stdout);

#endif // MARK

    while(~scanf("%d", &base)) {

        for(int i = 1; i <= 300; i++) {

            char *square = trans(i*i);

            if(judge(square)) {

                char *iStr = trans(i);

                int len1 = strlen(iStr);

                for(int i = len1-1; i >= 0; i--) {

                    printf("%c", iStr[i]);

                }

                printf(" ");

                int len2 = strlen(square);

                for(int i = len2-1; i >= 0; i--) {

                    printf("%c", square[i]);

                }

                printf("\n");

                delete(iStr);

            }

            delete(square);

        }

    }

    return 0;

}