题目描述
题目链接
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 类型保存余数了。
部分代码如下：
intmod(vector<int>&x, inta, intb) { intn=x.size(), q=0; for (inti=n-1; i>=0; --i) { q= (q*a+x[i]) %b; } returnq; }
大数除法类似，从 最高位开始除 ，并注意要把余数带到下一位，最后还得去掉前导 0 。
部分代码如下：
voiddiv(vector<int>&x, inta, intb) { intn=x.size(), q=0; for (inti=n-1; i>=0; --i) { x[i] +=q*a; q=x[i] %b; x[i] /=b; } for (inti=n-1; i>0; --i) { if (x[i]) break; x.pop_back(); } }
代码
c++
// string转化为vector<int>，倒序存储vector<int> s2i(string& s) { vector<int>x; intidx=0, n=s.size(); for (; idx<n; ++idx) { if (s[idx] !='0') break; } if (idx==n) idx=n-1; for (inti=n-1; i>=idx; --i) { x.push_back(s[i]-'0'); } returnx;} // a进制下x%b，x倒序存储int mod(vector<int>& x, int a, int b) { intn=x.size(), q=0; for (inti=n-1; i>=0; --i) { q= (q*a+x[i]) %b; } returnq;} // a进制下x/b，x倒序存储void div(vector<int>& x, int a, int b) { intn=x.size(), q=0; for (inti=n-1; i>=0; --i) { x[i] +=q*a; q=x[i] %b; x[i] /=b; } for (inti=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); intn=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; } intm=y.size(); stringres=""; for (inti=m-1; i>=0; --i) { res+='0'+y[i]; } returnres; } intmain() { intT; cin>>T; stringx; for (intt=0; t<T; ++t) { cin>>x; stringx2=convert(x, 10, 2); reverse(x2.begin(), x2.end()); stringres=convert(x2, 2, 10); cout<<"case #"<<t<<":"<<endl; cout<<res<<endl; } return0;}
python
x=int(input())foriinrange(x): print("case #%d:"%i) print(int(str(bin(int(input())))[2::][::-1], 2))
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
