每日算法系列【EOJ 3031】二进制倒置-阿里云开发者社区

每日算法系列【EOJ 3031】二进制倒置

2022-06-25 18

简介： 二进制倒置

+关注继续查看

题目描述

题目链接

https://acm.ecnu.edu.cn/problem/3031/

题解

while (n > 0) { 
    y.push_back(mod(x, a, b)); 
    div(x, a, b);  
    n = x.size(); 
    if (n == 1 && !x[0]) break;}

看起来非常简单，但是步骤 1 和 2 都涉及到了大数的求余和大数的除法算法，所以我们还得实现这两个算法。

大数求余只要从最高位开始计算的大小，并同时对求余，然后由于求余的加法和乘法定理，我们可以始终保持，这样就能用一个 int 类型保存余数了。

部分代码如下：

int mod(vector<int>& x, int a, int b) {  
    int n = x.size(), q = 0;  
    for (int i = n-1; i >= 0; --i) { 
        q = (q * a + x[i]) % b;  
    }    
    return q;
}

大数除法类似，从最高位开始除，并注意要把余数带到下一位，最后还得去掉前导 0 。

部分代码如下：

void div(vector<int>& x, int a, int b) {  
    int n = x.size(), q = 0;  
    for (int i = n-1; i >= 0; --i) {  
        x[i] += q * a;     
        q = x[i] % b;     
        x[i] /= b; 
    }   
    for (int i = n-1; i > 0; --i) { 
        if (x[i]) break; 
        x.pop_back();  
    
    }
}

代码

c++

#include <bits/stdc++.h>using namespace std;
// string转化为vector<int>，倒序存储vector<int> s2i(string& s) { 
vector<int> x;   
int idx = 0, n = s.size(); 
for (; idx < n; ++idx) {  
    if (s[idx] != '0') break;  
}  
if (idx == n) idx = n - 1; 
for (int i = n-1; i >= idx; --i) { 
    x.push_back(s[i]-'0'); 
}  
return x;}
// a进制下x%b，x倒序存储int mod(vector<int>& x, int a, int b) {  
int n = x.size(), q = 0;   
for (int i = n-1; i >= 0; --i) { 
    q = (q * a + x[i]) % b; 
}  
return q;}
// a进制下x/b，x倒序存储void div(vector<int>& x, int a, int b) {  
int n = x.size(), q = 0;  
for (int i = n-1; i >= 0; --i) { 
    x[i] += q * a;     
    q = x[i] % b;       
    x[i] /= b;   
}  
for (int i = n-1; i > 0; --i) { 
    if (x[i]) break;  
    x.pop_back();  
}
}
// a进制下s转化为b进制stringstring convert(string s, int a, int b) { 
vector<int> x = s2i(s);  
int n = x.size(); 
vector<int> y;    
while (n > 0) {   
    y.push_back(mod(x, a, b));    
    div(x, a, b);     
    n = x.size();      
    if (n == 1 && !x[0]) break;  
}  
int m = y.size();   
string res = "";   
for (int i = m-1; i >= 0; --i) {  
    res += '0' + y[i];  
} 
return res; }

int main() {  
    int T;   
    cin >> T;  
    string x;   
    for (int t = 0; t < T; ++t) { 
        cin >> x;    
        string x2 = convert(x, 10, 2);
        reverse(x2.begin(), x2.end());   
        string res = convert(x2, 2, 10); 
        cout << "case #" << t << ":" << endl;
        cout << res << endl;  
    }  
    return 0;}