小X转进制（平方回文数统计）

这道题的思路非常清晰：遍历1~N，计算每个数的平方 → 转M进制 → 判断是否是回文数 → 统计总数。

数据范围很小（N≤10000），直接暴力枚举完全没问题。

C++ 满分代码

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

// 功能1：将数字 x 转换成 M 进制字符串
string toBase(long long x, int m) {
    // 特殊：x=0 直接返回 "0"
    if (x == 0) return "0";
    
    char ch[] = "0123456789ABCDEF";
    string res;
    
    while (x > 0) {
        int rem = x % m;
        res += ch[rem];
        x = x / m;
    }
    
    // 得到的是逆序，翻转回来
    reverse(res.begin(), res.end());
    return res;
}

// 功能2：判断字符串是否是回文
bool isPalindrome(string s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;
    
    int cnt = 0;
    
    // 遍历 1~N
    for (int i = 1; i <= N; ++i) {
        // 计算平方（用 long long 防止溢出）
        long long square = (long long)i * i;
        // 转 M 进制
        string s = toBase(square, M);
        // 判断回文
        if (isPalindrome(s)) {
            cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

核心逻辑讲解

1. 遍历范围 循环 i = 1 到 N，逐个检查。

2. 计算平方 必须用 long long 存储，因为 10000² = 1亿，不会溢出，但保险起见统一用64位整数。

3. 进制转换 使用除 M 取余法，把平方数转成 M 进制字符串。

4. 回文判断 双指针法：左指针从头、右指针从尾，逐位对比是否相等，全部相等就是回文。

5. 统计答案 满足条件就计数+1，最后输出总数。

测试样例

输入：

2 10

过程：

• 1²=1 → 10进制"1" → 回文 ✔️
• 2²=4 → 10进制"4" → 回文 ✔️

输出：

2

总结

1. 核心步骤：枚举 → 平方 → 转进制 → 回文判断
2. 用 long long 避免平方溢出
3. 代码结构清晰，直接提交就能AC