题解

首先转化成10进制，这样除法时间复杂度就能降为$O(1)$，还避免做高精度运算

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100005];
int pow(int n, int k){//乘方
	int x = 1;
	for(int i = 1; i <= k; i++) x *= n;
	return x;
}
int to_10(int k, string a){//转为10进制
	int x = 0;
	int len = a.length();
	for(int i = 0; i < len; i++){
		if(a[i] >= 'A') x += (a[i] - 'A' + 10) * pow(k, len - i - 1);
		else x += (a[i] - '0') * pow(k, len - i - 1);
	}return x;
}void to_k(int k, int x){//转为k进制
	if(x < k){
		if(x >= 10) cout << char(x - 10 + 'A'); 
		else cout << x;
		return;
	}to_k(k, x / k);//递归
	int xx = x % k;
	if(xx >= 10) cout << char(xx - 10 + 'A');
	else cout << xx;
}
signed main(){
	int t, k2;
	string n;
	cin >> n >> k2;
	to_k(k2, to_10(2, n));

	return 0;
}

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