#include<bits/stdc++.h>
using namespace std;
const int Base=100000000,Len=8,N=10004;
int a[N],b[N],la,lb;
int Two(int x[],int&len){
if(x[1]%2){
return 0;
}
for(int i=len;i>=1;i--){
x[i-1]+=x[i]%2*Base;
x[i]/=2;
}
if(x[len]==0){
len--;
}
return Two(x,len)+1;
}
int Cmp(int x[],int y[]){//a>b
if(la!=lb){
return la>lb?1:-1;
}
for(int i=la;i>=1;i--){
if(x[i]>y[i]){
return 1;
}
if(x[i]<y[i]){
return -1;
}
}
return 0;
}
void Sub(int x[],int&lx,int y[],int&ly){
for(int i=1;i<=ly;i++){
x[i]-=y[i];
}
for(int i=1;i<=ly;i++){
if(x[i]<0){
x[i]+=Base;
x[i+1]--;
}
}
while(x[lx]==0&&lx>1){
lx--;
}
}
void Mul(int x[],int&lx,int v){
for(int i=1;i<=lx;i++){
x[i]*=v;
}
for(int i=1;i<=lx;i++){
x[i+1]+=x[i]/Base;
x[i]%=Base;
}
while(x[lx+1]!=0){
lx++;
}
}
string s1,s2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s1>>s2;
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
la=s1.size(),lb=s2.size();
for(int i=1;i<=la;i++){
a[(i-1)/Len+1]+=(s1[i-1]-'0')*pow(10,(i-1)%Len);
}
for(int i=1;i<=lb;i++){
b[(i-1)/Len+1]+=(s2[i-1]-'0')*pow(10,(i-1)%Len);
}
la=(la-1)/Len+1;
lb=(lb-1)/Len+1;
int Pow=min(Two(a,la),Two(b,lb));
while(1){
int res=Cmp(a,b);
if(res==1){
Sub(a,la,b,lb);
Two(a,la);
}
else if(res==-1){
Sub(b,lb,a,la);
Two(b,la);
}
else{
break;
}
}
for(int i=1;i<=Pow;i++){
Mul(a,la,2);
}
for(int i=la;i>=1;i--){
if(i!=la){
printf("%08d",a[i]);
}
else{
printf("%d",a[i]);
}
}
return 0;
}
这份TLE。
#include<bits/stdc++.h>
using namespace std;
int vbase = 100000000;
int vcnt = 8;
int a[100010];
int lena;
int b[100010];
int lenb;
int two(int x[], int& len) {
if (x[1] % 2) {
return 0;
}
for (int i = len; i >= 1; i--) {
x[i - 1] += x[i] % 2 * vbase;
x[i] /= 2;
}
if (x[len] == 0) {
len--;
}
return two(x, len) + 1;
}
bool equal(int x[], int y[]) {
if (lena != lenb) {
return false;
}
for (int i = 1; i <= lena; i++) {
if (x[i] != y[i]) {
return false;
}
}
return true;
}
int cmp(int x[], int y[]) {
if (lena != lenb) {
return lena > lenb ? 1 : -1;
}
for (int i = lena; i >= 1; i--) {
if (x[i] > y[i]) {
return 1;
}
if (x[i] < y[i]) {
return -1;
}
}
return 0;
}
void sub(int x[], int& lenx, int y[], int& leny) {
for (int i = 1; i <= leny; i++) {
x[i] -= y[i];
}
for (int i = 1; i <= leny; i++) {
if (x[i] < 0) {
x[i] += vbase;
x[i + 1]--;
}
}
while (x[lenx] == 0 && lenx > 1) {
lenx--;
}
}
void mul(int x[], int& lenx, int v) {
for (int i = 1; i <= lenx; i++) {
x[i] *= v;
}
for (int i = 1; i <= lenx; i++) {
x[i + 1] += x[i] / vbase;
x[i] %= vbase;
}
while (x[lenx + 1] != 0) {
lenx++;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
std::reverse(s1.begin(), s1.end());
std::reverse(s2.begin(), s2.end());
lena = s1.size();
lenb = s2.size();
for (int i = 1; i <= lena; i++) {
a[(i - 1) / vcnt + 1] += (s1[i-1] - '0') * pow(10, (i - 1) % vcnt);
}
for (int i = 1; i <= lenb; i++) {
b[(i - 1) / vcnt + 1] += (s2[i-1] - '0') * pow(10, (i - 1) % vcnt);
}
lena = (lena - 1) / vcnt + 1;
lenb = (lenb - 1) / vcnt + 1;
int power = min(two(a, lena), two(b, lenb));
while (1) {
int res = cmp(a, b);
if (res == 1) {
sub(a, lena, b, lenb);
two(a, lena);
}
else if (res == -1) {
sub(b, lenb, a, lena);
two(b, lenb);
}
else {
break;
}
}
for (int i = 1; i <= power; i++) {
mul(a, lena, 2);
}
for (int i = lena; i >= 1; i--) {
if (i != lena) {
printf("%08d", a[i]);
}
else {
printf("%d", a[i]);
}
}
return 0;
}
这份AC