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

+关注继续查看

## 题目描述

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;}

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;
}

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;}


### python

x = int(input())for i in range(x):
print("case #%d:" %i)
print(int(str(bin(int(input())))[2::][::-1], 2))

24 0

29 0
JAVA常见算法题(二十二)
package com.xiaowu.demo; //利用递归方法求5!。 public class Demo22 { public static void main(String[] args) { int n = 5; long s = sum(n); System.
641 0
JAVA常见算法题(一)
package com.xiaowu.demo; // 有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第四个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？ /** * * @author WQ * */ public class Demo...
481 0
jvm系列(三):java GC算法 垃圾收集器
GC算法 垃圾收集器 概述 垃圾收集 Garbage Collection 通常被称为“GC”，它诞生于1960年 MIT 的 Lisp 语言，经过半个多世纪，目前已经十分成熟了。 jvm 中，程序计数器、虚拟机栈、本地方法栈都是随线程而生随线程而灭，栈帧随着方法的进入和退出做入...
1281 0
JAVA算法系列 快速排序
java算法系列之排序 手写快排 首先说一下什么是快排，比冒泡效率要高，快排的基本思路是首先找到一个基准元素，比如数组中最左边的那个位置，作为基准元素key，之后在最左边和最右边设立两个哨兵，i 和 j 之后，开始按住左哨兵(i)，让右哨兵(j)往左走(j--)，找到比key小的元素后，按住右哨兵(...
800 0
Java利用IO流复制照片完整示例和详细分析
import java.io.FileInputStream; import java.io.FileOutputStream; /** * 该篇博客已经Deprecated,请参见I/O流的梳理和小结 * http://blog.
837 0
217

0