求助,样例过不了
查看原帖
求助,样例过不了
100690
lyhqwq楼主2022/3/11 19:37
#include<bits/stdc++.h>
using namespace std;
struct BIG{
	int d[1005];
	int len;
	BIG(){
		memset(d,0,sizeof(d));
		len=0;
	}
	void read(){
		string s;
		cin>>s;
		len=s.size();
		for(int i=0;i<len;i++){
			d[i-len]=s[i]-'0';
		}
		
	}
	void write(){
		for(int i=len;i>=1;i--){
			cout<<d[i];
		}
	} 
}one,two; 
BIG a,b;
int cnt;
BIG operator /(BIG a,int b){
	BIG c;
	int x=0;
	for(int i=1;i<=a.len;i++){
		c.d[i]=(x*10+a.d[i])/b;
		x=(x*10+a.d[i])%b;
	}
	int len1=0;
	while(c.d[len1]==0&&len1<a.len) len1++;
	for(int i=a.len;i>len1;i--){
		c.d[i-len1]=c.d[i];
	}
	c.len=len1;
	return c;
}
BIG operator -(BIG a,BIG b){
	BIG c;
	c.len=max(a.len,b.len);
	for(int i=1;i<=c.len;i++){
		if(a.d[i]<b.d[i]){
			c.d[i]+=a.d[i]-b.d[i]+10;
			c.d[i+1]-=1;
		}
		else{
			c.d[i]+=a.d[i]-b.d[i];
		}
	}
	return c; 
}
BIG operator *(BIG a,BIG b){
	BIG c;
	c.len=a.len+b.len-1;
	for(int i=1;i<=a.len;i++){
		for(int j=1;j<=b.len;j++){
			c.d[i+j-1]+=a.d[i]*b.d[j];
			c.d[i+j]+=c.d[i+j-1]/10;
			c.d[i+j-1]%=10;
		}
	}
	return c;
} 
BIG qpow(int p){
	if(p==0) return one;
	if(p==1) return two;
	BIG t=qpow(p/2);
	if(p%2==0) return t*t;
	if(p%2!=0) return t*t*two;
}
bool judge(BIG a,BIG b){
	if(a.len>b.len) return true;
	if(a.len<b.len) return false;
	else{
		for(int i=a.len;i>=1;i--){
			if(a.d[i]<b.d[i]) return false;
		}
		return true;
	}
}

int main(){
	a.read();
	b.read();
	while(a.len!=0&&b.len!=0){
		if(a.d[1]%2==0&&b.d[1]%2==0){
			cnt++;
			a=a/2;
			b=b/2;
		}
		else if(a.d[1]%2==0&&b.d[1]%2!=0){
			a=a/2;
		}
		else if(a.d[1]%2!=0&&b.d[1]%2==0){
			b=b/2;
		}
		else{
			if(judge(a,b)){
				a=a-b;
			}
			else b=b-a;
		}
	}
	one.len=two.len=1;
	one.d[1]=1;
	two.d[1]=2;
	if(a.len==0) ((BIG)(qpow(cnt)*b)).write();
	else ((BIG)(qpow(cnt)*a)).write();
}
2022/3/11 19:37
加载中...