20分TLE更相减损术
查看原帖
20分TLE更相减损术
735089
ECNUAT_LZX楼主2023/1/8 13:59
#include<bits/stdc++.h>
using namespace std;
struct Bigint{
	int len,Number[10005];
	inline void input(){
		string s;
		cin >> s;
		for(register int i=0,j=s.size()-1;i<s.size();i++,j--){
			Number[i]=s[j]-'0';
		}
		len=s.size();
	}
	inline void output(){
		for(register int i=len-1;i>=0;i--)printf("%d",Number[i]);
	}
}a,b;
inline void Div(Bigint &x,int k){
	long long n=0,m=0;
	for(register long long i=x.len-1;i>=0;i--){
        m=n*10+x.Number[i];
        x.Number[i]=m/k;
        n=m%k;
    }
    while(x.Number[x.len-1]==0){
    	x.len--;
	}
}
inline bool Max(Bigint x,Bigint y){
	if(x.len>y.len)return true;
	else if(y.len>x.len)return false;
	else{
		for(register int i=x.len-1;i>=0;i--){
			if(x.Number[i]>y.Number[i])return true;
			else if(x.Number[i]<y.Number[i])return false;
		}
	}
	
}
inline void Sub(Bigint &x,Bigint &y){
	if(Max(x,y)==true){
		int tw=0;
		for(register int i=0;i<x.len;i++){
			x.Number[i]=x.Number[i]-y.Number[i]-tw;
			if(x.Number[i]<0){
				tw=1;
				x.Number[i]+=10;
			}
			else{
				tw=0;
			}
		}
		while(x.Number[x.len-1]==0){
			x.len--;
		}
	}
	else{
		int tw=0;
		for(register int i=0;i<y.len;i++){
			y.Number[i]=y.Number[i]-x.Number[i]-tw;
			if(y.Number[i]<0){
				tw=1;
				y.Number[i]+=10;
			}
			else{
				tw=0;
			}
		}
		while(y.Number[y.len-1]==0){
			y.len--;
		}
	}
}
inline bool judge(Bigint x,Bigint y){
	if(x.len!=y.len)return 0;
	for(register int i=0;i<x.len;i++){
		if(x.Number[i]!=y.Number[i]){
			return 0;
		}
	}
	return 1;
}
long long sum=0;
inline void mul(Bigint &x,int k){
	int jw=0;
	for(register int i=0;i<x.len;i++){
		x.Number[i]=x.Number[i]*k+jw;
		jw=x.Number[i]/10;
		x.Number[i]%=10;
	}
	if(jw){
		x.Number[x.len++]=jw;
	}
}
signed main(){
	a.input();
	b.input();
	while(!a.Number[0]&1&&!b.Number[0]&1){
		if(!a.Number[0]&1)Div(a,2);
		if(!b.Number[0]&1)Div(b,2);
		sum++;
	}
	while(!judge(a,b)){
		Sub(a,b);
	}
	while(sum--){
		mul(a,2);
	}
	a.output();
	return 0;
}



2023/1/8 13:59
加载中...