bzoj 1876: [SDOI2009]SuperGCD （高精度+gcd）

Description

Input

Output

Sample Input

Sample Output

HINT

对于20%的数据，0 < A , B ≤ 10 ^ 18。对于100%的数据，0 < A , B ≤ 10 ^ 10000。

Source

Day1

题解：高精度+gcd

刚开始写的方法TLE了，所以照着网上的姿势写的。。。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100006#define inf 100000000#define mx 1252using namespace std;char s[N],s1[N];struct data{	int len,s[mx+10];	data() {		memset(s,0,sizeof(s));	}	int &Operator [](int i) {		return s[i];	}	void operator /=(int x){		for (int i=mx;i>=1;i--) 		 s[i-1]+=s[i]%x*inf,s[i]/=x;	}	void operator -=(data &b) {		for (int i=1;i<mx;i++) 		s[i]=s[i]-b[i]+(s[i-1]+inf)/inf-1,s[i-1]=(s[i-1]+inf)%inf;	}	data operator *=(int x){		for (int i=1;i<mx;i++) 		s[i]=s[i]*x+s[i-1]/inf,s[i-1]%=inf;	}	bool operator > (data &b) {		for (int i=mx;i>=1;i--) 			if (b[i]!=s[i]) return s[i]>b[i];		return 0;	}	void PRint() {		int p=mx;		while (!s[p]&&p>0) p--;		printf("%d",s[p--]);		while (p) printf("%08d",s[p--]);		putchar('/n');	}	bool iszero() {		for (int i=1;i<mx;i++)		 if (s[i]!=0) return 0;		return 1;	}	void read() {         char tp[10010]={'0','0','0','0','0','0','0','0'};         		 scanf("%s",tp+8);         int L=strlen(tp+1),p=1;         while(L-8*p+1>0)             		  sscanf(tp+L-8*p+++1,"%08d",&s[p]);    }}a1,b1;data gcd(data a,data b){     int g=0; bool x,y;	while (!a.iszero()&&!b.iszero()) {		x=!(a[1]&1); y=!(b[1]&1);		if (x&&y) g++,a/=2,b/=2;		else if (x||y) {			if (x) a/=2; 			if (y) b/=2;		}		else {			if (a>b) a-=b;			else b-=a;		}	}	if (b>a) a=b;	for (int i=0;i<g;i++) a*=2;	a.print();}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	a1.read(); b1.read();	gcd(a1,b1);}