题目描述

回文数是指从左向右念和从右向左念都一样的数。如 12321 就是一个典型的回文数。

给定一个用十进制表示的正整数 B，输出所有 [1,300] 中，它的平方用 B 进制表示时是回文数的数。

输入格式

共一行，一个单独的正整数 B。

输出格式

每行两个 B 进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。

注意大于 9 的数，用字母表示。如用 A 表示 10，B 表示 11，用第 n 个大写字母表示 n+9。

输入输出样例

输入 #1

10

输出 #1

1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

说明/提示

【数据范围】
对于 100% 的数据，2≤B≤20

题目翻译来自NOCOW。

USACO Training Section 1.2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 将十进制数转换为指定进制的字符串表示
string toBase(int num, int base) {
    string result;
    while (num > 0) {
        int digit = num % base;
        if (digit < 10) {
            result += (char)('0' + digit);  // 将数字转换为字符并追加到结果字符串
        } else {
            result += (char)('A' + digit - 10);  // 将大于等于10的数字转换为对应的大写字母并追加到结果字符串
        }
        num /= base;  // 去掉最低位
    }
    reverse(result.begin(), result.end());  // 将结果字符串翻转，得到最终的进制表示
    return result;
}

// 判断一个字符串是否是回文字符串
bool isPalindrome(string s) {
    int len = s.length();
    for (int i = 0; i < len / 2; ++i) {
        if (s[i] != s[len - i - 1]) {
            return false;  // 如果存在不对称的字符，则不是回文字符串
        }
    }
    return true;  // 所有字符都对称，则是回文字符串
}

int main() {
    int B;
    cin >> B;  // 读入进制数

    for (int i = 1; i <= 300; ++i) {
        int square = i * i;  // 计算平方
        string baseB = toBase(i, B);  // 将当前数转换为指定进制的字符串表示
        string baseSquare = toBase(square, B);  // 将平方数转换为指定进制的字符串表示
        if (isPalindrome(baseSquare)) {  // 判断平方数的进制表示是否为回文字符串
            cout << baseB << " " << baseSquare << endl;  // 输出满足条件的数及其平方的进制表示
        }
    }

    return 0;
}