进制数a_八进制转换为二进制最简单的方法

1. 题目来源

链接：3373. 进制转换

链接：3374. 进制转换2

相关：[高精度+模板] 高精度整数加、减、乘、除模板

2. 题目解析

主要解决进制转换的几个问题，属于模板题，隶属于模拟大类，并练习高精度+短除法代码实现。

$a$ 进制转 10 进制：

• 通用秦九韶算法即可，秦九韶算法与短除法互为逆运算。

10 进制转 $a$ 进制：

• 高精度除法，短除法。
• 例题：3373. 进制转换

$a$ 进制转 $b$ 进制：

• 直接进行进制转换，中间不经过 10 进制。高精度只涉及高精除。
• 高精度除法，短除法。
• 例题：3374. 进制转换2

时间复杂度分析：

• 以 3374. 进制转换2 为例。
• 内层 for 循环是 $O(k)$，$k$ 为数 $n$ 的位数。
• 外层，每次数值 $n$ 都会除以 $b$，总共会除 $lo{g}_b^n$ 次。
• 其中，$n$ 的位数 $k$，在 $a$ 进制下即为 $lo{g}_a^n$。
• 简单处理一下，可发现 $\frac{lo{g}_b^n}{lo{g}_a^n}=lo{g}_a^b$，即比值为一个常数。
• 则外层迭代次数就是差不多和内层 $O(k)$ 一个级别的常数，两者相乘，总的时间复杂度为 $O(k^2)$。

时间复杂度：$O(k^2)$

空间复杂度：$O(lo{g}_a^n)$

采用高精度除法模板，实现即可，注意体会与模板的不同之处！看注释！

3373. 进制转换

#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; vector<int> div(vector<int> &A, int b) { 
    vector<int> C; for (int i = A.size() - 1, r = 0; ~i; i -- ) { 
    r = r * 10 + A[i]; C.push_back(r / b); r %= b; } // 先取得 C 的高位，但本身需要倒着存，故反转 reverse(C.begin(), C.end()); // while (C.size() > 1 && C.back() == 0) C.pop_back(); 这样的写法是错误的， // 会死循环，返回的 C 中元素个数一直大于 1 ，主函数内部 while (A.size()) 死循环。 // 故，一位数的时候，仍需要继续除，直到除成商为 0，然后 pop_back(); // 所以单个商为 0 的情况在此会忽略，即输入为 0 时，前导 0 的情况需要特判 while (C.size() && C.back() == 0) C.pop_back(); // 在此不必反转，持续做短除法，直至将 A 除没。 return C; } int main() { 
    string s; while (cin >> s) { 
    vector<int> A; for (int i = s.size() - 1; ~i; i -- ) A.push_back(s[i] - '0'); // 从高位到低位 string res; // 这个写法很巧妙。div 中的 while 不必判断单个 0 的情况 // // 其实这个判断是不用的，在 0 这个特殊情况在 while 中已经包含了 if (s == "0") cout << 0 << endl; else { 
    while (A.size()) { 
    // 开始短除法，越除位数越少 res += to_string(A[0] % 2); // 二进制，余数模 2 即为个位数字。注意在此顺序是颠倒的 A = div(A, 2); } // 短除法，余数从下往上是结果。在这需要反转 reverse(res.begin(), res.end()); cout << res << endl; } } return 0; } 

复习：

• 高精除，返回余数：

#include <bits/stdc++.h> using namespace std; vector<int> div(vector<int> &A, int b, int &r) { 
    vector<int> C; for (int i = A.size() - 1; ~i; i -- ) { 
    r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() && C.back() == 0) C.pop_back(); return C; } int main() { 
    string s; while (cin >> s) { 
    vector<int> A; for (int i = s.size() - 1; ~i; i -- ) A.push_back(s[i] - '0'); string res; while (A.size()) { 
    int r = 0; A = div(A, 2, r); res += to_string(r); } reverse(res.begin(), res.end()); cout << res << endl; } return 0; } 

更为灵活的实现方式，直接在循环中原地算法解决！

#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; int main() { 
    int a, b; string s; cin >> a >> b >> s; vector<int> A; for (int i = s.size() - 1; ~i; i -- ) { 
    if (s[i] >= 'A') A.push_back(s[i] - 'A' + 10); // A-->10，B-->11 else A.push_back(s[i] - '0'); } string res; while (A.size()) { 
    int r = 0; for (int i = A.size() - 1; ~i; i -- ) { 
    A[i] += r * a; // 很巧妙的原地算法 r = A[i] % b; A[i] /= b; /* 均可 r = r * a + A[i]; A[i] = r / b; r %= b; */ } while (A.size() && A.back() == 0) A.pop_back(); if (r < 10) res += to_string(r); else res += r - 10 + 'a'; } reverse(res.begin(), res.end()); cout << res << endl; return 0; }