BZOJ1876: [SDOI2009]SuperGCD

                      1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<cstdlib>
  7 #include<vector>
  8usingnamespace std;
  9 typedef longlong ll;
 10 typedef longdouble ld;
 11 typedef pair<int,int> pr;
 12constdouble pi=acos(-1);
 13#define rep(i,a,n) for(int i=a;i<=n;i++)
 14#define per(i,n,a) for(int i=n;i>=a;i--)
 15#define Rep(i,u) for(int i=head[u];i;i=Next[i])
 16#define clr(a) memset(a,0,sizeof(a))
 17#define pb push_back
 18#define mp make_pair
 19#define fi first
 20#define sc second
 21#define pq priority_queue
 22#define pqb priority_queue <int, vector<int>, less<int> >
 23#define pqs priority_queue <int, vector<int>, greater<int> >
 24#define vec vector
 25 ld eps=1e-9;
 26 ll pp=1000000007;
 27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
 28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
 29//void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
 30//void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 31int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
 32 ll read(){ ll ans=0; char last=‘‘,ch=getchar();
 33while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
 34while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
 35if(last==‘-‘)ans=-ans; return ans;
 36}
 37#define P 1000000000
 38#define N 10005
 39char ch[N];
 40struct Hp{
 41int len,nu[N/9+5];
 42    Hp(){
 43         len=0; memset(nu,0,sizeof(nu));
 44    }
 45void read(){
 46         scanf("%s",ch); int slen=strlen(ch);
 47if (slen%9==0) len=slen/9;
 48else len=slen/9+1;
 49for (int i=1;i<=len;i++){
 50int g=1;
 51for (int j=0;j<9;j++)
 52if (slen-1-(i-1)*9-j>=0) {
 53                 nu[i]+=(ch[slen-1-(i-1)*9-j]-‘0‘)*g;
 54                 g*=10; 
 55            }
 56        }
 57    }
 58void div2(){
 59for (int i=len;i>0;i--) {
 60if (nu[i]&1) nu[i-1]+=P;
 61             nu[i]>>=1;
 62        }
 63if (nu[len]==0) len--;
 64    }
 65void mul2(){
 66for (int i=1;i<=len;i++) nu[i]<<=1;
 67for (int i=1;i<=len;i++) 
 68if (nu[i]>=P) nu[i]-=P,nu[i+1]++;
 69if (nu[len+1]>0) len++;
 70    }
 71     friend booloperator >(Hp a,Hp b){
 72if (b.len>a.len) return0;
 73if (b.len<a.len) return1;
 74for (int i=a.len;i>0;i--){
 75if (a.nu[i]>b.nu[i]) return1;
 76if (a.nu[i]<b.nu[i]) return0;
 77        }
 78return1;
 79    }
 80     friend Hp operator -(Hp a,Hp b){
 81         Hp c; c.len=a.len;
 82for (int i=a.len;i>0;i--)
 83             c.nu[i]=a.nu[i]-b.nu[i];
 84for (int i=1;i<=c.len;i++)
 85if (c.nu[i]<0) c.nu[i+1]--,c.nu[i]+=P;
 86while (c.nu[c.len]==0&&c.len) c.len--;
 87return c; 
 88    }
 89bool z(){
 90for (int i=len;i>0;i--)
 91if (nu[i]>0) return0;
 92return1;
 93    }
 94voidout(){
 95for (int i=len;i>0;i--) 
 96if (i==len) printf("%d",nu[i]);
 97else printf("%09d",nu[i]);
 98    }
 99};
100int main()
101{
102     Hp a,b; a.read(); b.read(); int num=0;
103while(1)
104    {
105if((a.nu[1]%2==0)&&(b.nu[1]%2==0)){a.div2();b.div2();num++;}
106elseif((a.nu[1]%2==0)) a.div2();
107elseif((b.nu[1]%2==0)) b.div2();
108if(a>b){a=a-b; if(a.z()){while(num--)b.mul2();b.out();break;}}
109else {b=b-a; if(b.z()){while(num--)a.mul2();a.out();break;}}
110    }
111return0;
112  }