高精度+GCD
唔……高精gcd其实可以这么算：
\[ GCD(a,b)= \begin{cases} a & b=0 \\ 2*GCD(\frac{a}{2},\frac{b}{2}) & a\mod 2=0,b \mod 2=0 \\ GCD(\frac{a}{2},b) & a\mod 2=0,b \mod 2=1 \\ GCD(a,\frac{b}{2}) & a\mod 2=1,b \mod 2=0 \\ GCD(b,a-b) & else \end{cases} \]
然而Windows下栈空间只有8M坑爹啊……本地根本不能跑大数据。。。然后一直挂……
只好把大部分操作都改成void类型，并且传引用，然后把gcd的过程改成对全局变量进行操作……并不传参数……
各种乱搞一气终于是过了这道模板题……sad
/**************************************************************
Problem: 1876
User: Tunix
Language: C++
Result: Accepted
Time:1860 ms
Memory:1556 kb
****************************************************************/ //BZOJ 1876
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ struct bint{
int v[N];
int l;
bint(){l=; memset(v,,sizeof v);}
int& operator [] (int x){return v[x];}
}a,b,r,t; const int Limit=;
//const LL Limit=10000000000000000LL;
//1e16
void print(bint a){
printf("%d",a[a.l]);
D(i,a.l-,) printf("%09d",a[i]);
puts("");
}
bint operator - (bint a,bint b){
F(i,,a.l){
a[i]-=b[i];
if (a[i]<) a[i]+=Limit,a[i+]--;
}
while(a.l && a[a.l]==) a.l--;
return a;
}
void div2(bint& a){
F(i,,a.l){
if (a[i]&) a[i-]+=Limit/;
a[i]>>=;
}
while(a.l && a[a.l]==) a.l--;
} void mul2(bint &a){
D(i,a.l,){
a[i]<<=;
a[i+]+=a[i]/Limit;
a[i]%=Limit;
}
while (a[a.l+]>) a.l++;
}
bool operator < (bint a,bint b){
if (a.l!=b.l) return a.l<b.l;
D(i,a.l,){
if (a[i]!=b[i]) return a[i]<b[i];
}
return ;
}
void gcd(){
if (b.l==){
r=a; return;
}
if (!(a[]&) && !(b[]&)){
div2(a),div2(b); gcd(); mul2(r); return;
}
if (!(a[]&) && (b[]&)){
div2(a); gcd(); return;
}
if ((a[]&) && !(b[]&)){
div2(b); gcd(); return;
}
if (a<b) swap(a,b);
t=b; b=a-b; a=t;
gcd();
}
char s1[],s2[]; int main(){
#ifndef ONLINE_JUDGE
freopen("1876.in","r",stdin);
freopen("1876.out","w",stdout);
#endif
scanf("%s%s",s1+,s2+);
int l1=strlen(s1+),l2=strlen(s2+);
a.l=l1/+bool(l1%);
b.l=l2/+bool(l2%);
F(i,,a.l){
int k1=max(,l1-i*+),k2=l1-(i-)*;
F(j,k1,k2) a[i]=a[i]*+s1[j]-'';
}
F(i,,b.l){
int k1=max(,l2-i*+),k2=l2-(i-)*;
F(j,k1,k2) b[i]=b[i]*+s2[j]-'';
}
gcd();
print(r);
return ;
}
1876: [SDOI2009]SuperGCD
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1826 Solved: 589
[Submit][Status][Discuss]
Description
Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约
数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比
赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。
数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比
赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。
Input
共两行：
第一行：一个数A。
第二行：一个数B。
第一行：一个数A。
第二行：一个数B。
Output
一行，表示A和B的最大公约数。
Sample Input
12
54
54
Sample Output
6
HINT
对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。