你好！我是你的OI教练。很高兴看到你继续挑战进制转换的题目。

上一题我们做的是“$K$ 进制转十进制”，这道题（B3849）是它的逆运算：“十进制转 $R$ 进制”。这同样是计算机科学最底层的逻辑之一，叫做“短除法”。

让我们拿出草稿纸，把这个逆向过程推导清楚。

1. 读题关键词：你的“雷达”响了吗？

1. $R$ 进制 ($2 \le R \le 36$)：
   • 这意味着除了数字 0-9，还需要用大写字母 A-Z 来表示 10-35。
   • 你需要建立一个映射表：0->'0', ..., 9->'9', 10->'A', ..., 35->'Z'。
2. 正整数 $N$ ($1 \le N \le 10^6$)：
   • 数据范围很小，int 足够。
   • “正整数”意味着 $N \ge 1$，不需要特殊处理 $N=0$ 的情况（虽然健壮的代码通常会处理）。
3. 逆序输出：
   • 这是短除法最大的坑。算出来的最后一位其实是结果的最后一位（最低位），但输出时是从最高位开始。所以需要倒序。

2. 预备知识点

• 取模 (%) 和除法 (/)：
  • % 用来获取当前最低位的数值（余数）。
  • / 用来“砍掉”已经处理完的最低位。
• 数组/字符串查表法：
  • 用一个字符串 const string table = "0123...XYZ"; 来代替复杂的 if-else 判断，速度快且代码短。
• 栈（Stack）或 字符串反转：
  • 因为计算顺序和输出顺序相反，需要先存起来再反过来输出。

3. 启发式教学：草稿纸上的推演

我们以样例输入 $N=123, R=25$ 为例。我们需要不断地把 $N$ 除以 $R$，取余数。

得到的序列是：先是 'N'，后是 '4'。 正确的读法（从下往上）：4N。

教练画图： 你可以把这个过程想象成剥洋葱，也可以想象成不断的打包。 你有 123 个苹果，每 25 个装一箱。

• 先装满 4 箱（高位），剩下 23 个散的（低位）。
• 我们算的时候，总是先算出“散的”余数，最后才算出“最大的箱子”。
• 所以输出时必须反过来。

4. 标准代码 (NOIP C++14)

/**
 * 题目：B3849 [GESP样题 三级] 进制转换
 * 考点：短除法、取模运算、字符映射
 * 难度：普及- / GESP三级
 */

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // 用于 reverse 函数

using namespace std;

// 建立索引表，下标 0-35 对应题目要求的字符
// 这种写法比写 if(x>=10) char = x-10+'A' 要快且不易写错
const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void solve() {
    int n, r;
    // 题目输入格式：两行，第一行N，第二行R
    if (!(cin >> n >> r)) return; 

    // 特判：虽然题目说正整数，但如果N=0，应该输出0
    if (n == 0) {
        cout << "0" << endl;
        return;
    }

    string ans = "";
    
    // 短除法核心逻辑
    while (n > 0) {
        int remainder = n % r;  // 取余数
        ans += DIGITS[remainder]; // 查表得到字符，拼接到字符串末尾
        n /= r;                 // 除以进制，准备算下一位
    }

    // 此时 ans 存的是最低位到最高位（例如 "N4"）
    // 需要反转字符串得到正确顺序（"4N"）
    reverse(ans.begin(), ans.end());

    cout << ans << endl;
}

int main() {
    // IO优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

5. 数据生成器 (1.in - 10.in)

这份代码会生成覆盖各种情况的测试数据，特别是边界的进制（2进制和36进制）。

/**
 * B3849 数据生成器
 * 生成 1.in/1.out ~ 10.in/10.out
 */

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
string solve(int n, int r) {
    if (n == 0) return "0";
    string ans = "";
    int tempN = n;
    while (tempN > 0) {
        ans += DIGITS[tempN % r];
        tempN /= r;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

// ==========================================
// Part 2: 数据构造逻辑
// ==========================================
int randInt(int min, int max) {
    return rand() % (max - min + 1) + min;
}

void makeData(int fileId) {
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    
    ofstream fin(inName);
    ofstream fout(outName);
    
    int N, R;
    
    // 题目范围: 1 <= N <= 10^6, 2 <= R <= 36
    
    if (fileId <= 3) {
        // 1-3: 基础数据，常见进制
        N = randInt(1, 100);
        int bases[] = {2, 8, 10, 16};
        R = bases[randInt(0, 3)];
    } else if (fileId <= 5) {
        // 4-5: 中等数据，随机进制
        N = randInt(100, 10000);
        R = randInt(2, 36);
    } else if (fileId == 6) {
        // 6: 边界 - 二进制 (结果最长)
        N = randInt(500000, 1000000);
        R = 2;
    } else if (fileId == 7) {
        // 7: 边界 - 36进制 (结果最短，含字母)
        N = randInt(500000, 1000000);
        R = 36;
    } else if (fileId == 8) {
        // 8: 边界 - 刚刚超过10的进制，测试 'A'
        N = randInt(10000, 100000);
        R = 11;
    } else {
        // 9-10: 最大数据
        N = randInt(900000, 1000000);
        R = randInt(2, 36);
    }
    
    // 写入 .in (题目格式: 第一行N, 第二行R)
    fin << N << endl;
    fin << R << endl;
    
    // 写入 .out
    fout << solve(N, R) << endl;
    
    fin.close();
    fout.close();
    
    cout << "Generated Case " << fileId << ": N=" << N << ", R=" << R << endl;
}

int main() {
    srand((unsigned)time(NULL)); 
    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    cout << "All done." << endl;
    return 0;
}

教学提示

这道题和上一道题（$K$ 转 10）合在一起，就是完整的进制转换知识体系。

1. 转 10 进制：用乘法（秦九韶），从左到右累加。
2. 转 $R$ 进制：用除法/取模，从低位到高位生成，最后记得反转。

建议让学生把这两段代码背后的数学过程在纸上各画一遍，对比记忆。